Search
Abstract
Recently, Behr (2020) introduced a notion of the chromatic index of signed graphs and proved that for every signed graph (G, σ) it holds that ∆(G) ≤ χ′(G,σ) ≤ ∆(G) + 1, where ∆(G) is the maximum degree of G and χ′ denotes its chromatic index. In general, the chromatic index of (G, σ) depends on both the underlying graph G and the signature σ. In the paper we study graphs G for which χ′(G, σ) does not depend on σ. To this aim we introduce two new classes of graphs, namely 1± and 2±, such that graph G is of class 1± (respectively, 2±) if and only if χ′(G, σ) = ∆(G) (respectively, χ′(G, σ) = ∆(G) + 1) for all possible signatures σ. We prove that all wheels, necklaces, complete bipartite graphs Kr,t with r ̸= t and almost all cacti graphs are of class 1±. Moreover, we give sufficient and necessary conditions for a graph to be of class 2±, i.e. we show that these graphs must have odd maximum degree and give examples of such graphs with arbitrary odd maximum degree bigger than 1.
Citations
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Authors (3)
-
Krzysztof Turowski dr inż.
-
Bartłomiej Wróblewski
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach
- Published in:
-
DISCRETE APPLIED MATHEMATICS
no. 338,
pages 311 - 319,
ISSN: 0166-218X - Language:
- English
- Publication year:
- 2023
- Bibliographic description:
- Janczewski R., Turowski K., Wróblewski B.: Edge coloring of graphs of signed class 1 and 2// DISCRETE APPLIED MATHEMATICS -Vol. 338, (2023), s.311-319
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.dam.2023.06.029
- Sources of funding:
-
- COST_FREE
- Verified by:
- Gdańsk University of Technology
seen 17 times
Recommended for you
Minimum order of graphs with given coloring parameters
- G. Bacsó,
- P. Borowiecki,
- M. Hujter
- + 1 authors