Wyszukiwarka
Abstrakt
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.
Cytowania
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Autorzy (3)
-
Krzysztof Turowski dr inż.
-
Bartłomiej Wróblewski
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach
- Opublikowano w:
-
DISCRETE APPLIED MATHEMATICS
nr 338,
strony 311 - 319,
ISSN: 0166-218X - Język:
- angielski
- Rok wydania:
- 2023
- Opis bibliograficzny:
- 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:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2023.06.029
- Źródła finansowania:
-
- Publikacja bezkosztowa
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 63 razy
Publikacje, które mogą cię zainteresować
Minimum order of graphs with given coloring parameters
- G. Bacsó,
- P. Borowiecki,
- M. Hujter
- + 1 autorów