Edge coloring of graphs of signed class 1 and 2

Abstract

Recently, Behr introduced a notion of the chromatic index of signed graphs and proved that for every signed graph $(G$, $\sigma )$ it holds that \[ Δ(G)\leqχ'(G\text{, }σ)\leqΔ(G)+1\text{,} \] where $\Delta (G)$ is the maximum degree of $G$ and ${\chi }^{\prime }$ denotes its chromatic index. In general, the chromatic index of $(G$, $\sigma )$ depends on both the underlying graph $G$ and the signature $\sigma$. In the paper we study graphs $G$ for which ${\chi }^{\prime }(G$, $\sigma )$ does not depend on $\sigma$. To this aim we introduce two new classes of graphs, namely $1^{\pm }$ and $2^{\pm }$, such that graph $G$ is of class $1^{\pm }$ (respectively, $2^{\pm }$) if and only if ${\chi }^{\prime }(G$, $\sigma )=\Delta (G)$ (respectively, ${\chi }^{\prime }(G$, $\sigma )=\Delta (G)+1$) for all possible signatures $\sigma$. We prove that all wheels, necklaces, complete bipartite graphs $K_{r,t}$ with $r\ne t$ and almost all cacti graphs are of class $1^{\pm }$. Moreover, we give sufficient and necessary conditions for a graph to be of class $2^{\pm }$, i.e. we show that these graphs must have odd maximum degree and give examples of such graphs with arbitrary odd maximum degree bigger that $1$.