Edge coloring of signed graphs (Q2185748): Difference between revisions

A signed graph \((G,\sigma)\) is a graph \(G\) with a signature \(\sigma:E(G)\to\{+1,-1\},\) where \(G\) is the underlying graph of \((G,\sigma)\). \textit{T. Zaslavsky} [Discrete Math. 39, 215--228 (1982; Zbl 0487.05027)] started the study of vertex coloring of signed graphs which is to color all vertices of a signed graph \((G,\sigma)\) by a mapping \(c:V(G)\to\{0,\pm 1,\dots,\pm k\}\) such that \(c(u) \neq\sigma(uv)\), \(c(v),\forall uv\in E(G)\). In this case, the chromatic number of signed graphs is an invariant under switching since the colors can be inverted. However, it is not an extension of the chromatic number of graphs. In this article, the authors introduce an edge coloring for signed graphs that is naturally corresponding to the vertex coloring of their signed line graphs. Let \(\chi_\pm(G,\sigma)\) denote the edge chromatic number of a signed graph \((G,\sigma)\). It follows from the definition that \(\chi^\prime_\pm(G,\sigma)\geq\Delta\), where \(\Delta\) is the maximum degree of \(G\). The authors try to find a Vizing-type theorem for \(\chi^\prime_\pm(G,\sigma)\), and they show that \(\chi^\prime_\pm(G,\sigma)\leq\Delta + 1\) if \(\Delta\leq 5\) or if \(G\) is a planar graph. Also, the authors establish that every planar graph with \(\Delta=8\) and without adjacent triangles has a linear 4-coloring, which confirm the planar linear arboricity conjecture for this family of graphs. A direct application of this result shows that \(\chi_\pm(G,\sigma)=\Delta\) if \(G\) is a planar graph with \(\Delta\geq 10\) or \(G\) is a planar graph with \(\Delta\in\{8,9\}\) and without adjacent triangles. The authors pose the following two open problems. 1. Characterize all signed graphs \((G,\sigma)\) such that \(\chi^\prime_\pm(G,\sigma) =\chi^\prime(G)\). 2. For every signed graph \((G,\sigma)\), \(\chi^\prime_\pm(G,\sigma)\leq\chi^\prime(G) + 1\) or even \(\chi^\prime_\pm(G,\sigma)\leq\chi^\prime(G) + 2\). This paper contains useful information related to signed graphs.