The entire coloring of series-parallel graphs
The entire chromatic number \(\chi_{\text{vef}}(G)\) of a plane graph \(G\) is the minimum number of colors needed for coloring the vertices, edges and the faces of \(G\) such that no two adjacent or incident mentioned elements of \(G\) are of the same color. \textit{H. V. Kronk} and \textit{J. Mitchem} [Discrete Math. 5, 255--260 (1973; Zbl 0256.05106)] conjectured that for every plane graph \(G\), \(\Delta(G) + 1 \leq \chi_{\text{vef}}(G) \leq \Delta(G) + 4\) holds. In this paper, it is proved that this conjecture holds for series--parallel graphs (that is, the graphs containing no subgraph homeomorphic to \(K_4\)); more precisely, it is shown that if \(G\) is a series-parallel graph, then \(\chi_{\text{vef}}(G) \leq \max\{8,\Delta(G)+2\}\) and \(\chi_{\text{vef}}(G) = \Delta(G)+1\) if \(G\) is 2-connected and \(\Delta(G) \geq 6\).
- A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
- A seven-color theorem on the sphere
- Colouring series-parallel graphs
- scientific article; zbMATH DE number 790475 (Why is no real title available?)
- scientific article; zbMATH DE number 2192154 (Why is no real title available?)
- On the colorings of outerplanar graphs
- On the Entire Coloring Conjecture
- Planar graphs: Theory and algorithms
- Structural theorem on plane graphs with application to the entire coloring number
- Structure of neighborhoods of edges in planar graphs and simultaneous coloring of vertices, edges and faces
- The linear arboricity of series-parallel graphs
- Topology of series-parallel networks
- Entire choosability of near-outerplane graphs
- Acyclic edge colorings of planar graphs and series parallel graphs
- List total colorings of series-parallel graphs
- List edge-colorings of series-parallel graphs
- Multicolorings of series-parallel graphs
- Acyclic edge coloring of graphs with large girths
- Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs
- The entire choosability of plane graphs
- On \(r\)-acyclic edge colorings of planar graphs
- Structural theorem on plane graphs with application to the entire coloring number
This page was built for publication: The entire coloring of series-parallel graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2577645)
