Edge coloring of signed graphs
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.
- COVERING AND PACKING IN GRAPHS, I.
- Graph theory
- Graph theory
- scientific article; zbMATH DE number 3717365 (Why is no real title available?)
- scientific article; zbMATH DE number 1299961 (Why is no real title available?)
- On the Laplacian coefficients of signed graphs
- Signed graph coloring
- Signed graphs
- Some results on linear arboricity
- SOME UNSOLVED PROBLEMS IN GRAPH THEORY
- The chromatic number of a signed graph
- The Factorization of Linear Graphs
- The linear arboricity of planar graphs of maximum degree seven is four
- The linear arboricity of some regular graphs
- Edge coloring of the signed generalized Petersen graph
- Edge coloring signed graphs
- Signed coloring of 2-dimensional grids
- The complexity of signed graph and edge-coloured graph homomorphisms
- Vizing's adjacency lemma on edge chromatic critical signed graphs and its applications
- A note on the vertex arboricity of signed graphs
- Coloring problem of signed interval graphs
- Degree choosable signed graphs
- Signed planar graphs with \(\Delta \geq 8\) are \(\Delta\)-edge-colorable
- On colorings and orientations of signed graphs
- Edge coloring of graphs of signed class 1 and 2
- Bounds for the chromatic index of signed multigraphs
- The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree
- The edge coloring of the Cartesian product of signed graphs
- An adjacency lemma on signed edge colorings with an application to planar graphs
This page was built for publication: Edge coloring of signed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2185748)
