The entire coloring of series-parallel graphs (Q2577645): Difference between revisions

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\).