Repozytorium publikacji - Politechnika Gdańska

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.

Autorzy

• dr hab. inż. Robert Janczewski link otwiera się w nowej karcie ,
• dr inż. Krzysztof Turowski,
• Bartłomiej Wróblewski