Total-coloring of sparse graphs with maximum degree 6 (Q2240657)

Given a graph \(G=(V, E)\) and a positive integer \(k\), a \(k\)-total-coloring of \(G\) is a mapping \(\phi: V \cup E \rightarrow\) \(\{1,2, \dots, k\}\) such that no two adjacent or incident elements receive the same color. The total chromatic number \(\chi^{\prime\prime}(G)\) of \(G\) is the smallest integer \(k\) such that \(G\) is \(k\)-total-colorable. Clearly, \(\chi^{\prime\prime}(G)\geq \Delta +1\). \textit{V. G. Vizing} [Usp. Mat. Nauk 23, No. 6(144), 117--134 (1968; Zbl 0177.52301)] (see also [\textit{M. Behzad}, Graphs and their chromatic number. East Lansing, MI: Michigan State University (PhD Thesis) (1965)]) proposed the conjecture, now known as, the total coloring conjecture, which states that every graph of maximum degree \(\Delta\) admits a \((\Delta+2)\)-total-coloring, that is, \(\chi^{\prime\prime}(G) \leq \Delta +2\). This conjecture has been verified for \(\Delta \leq 5\), and it is still open when \(\Delta=6\), even for planar graphs. Let \(\operatorname{mad}(G)\) denote the maximum average degree of the graph \(G \) and is defined by \(\operatorname{mad}(G)=\) \(\max \left\{\frac{2|E(H)|}{|V(H)|}: H \subseteq G\right\}\). In this paper, the authors investigated the total coloring conjecture for sparse graphs with maximum degree 6 and proved the following result. Theorem: Let \(G\) be a graph with maximum degree \(\Delta(G)=6\) and \(\operatorname{mad}(G)<23 / 5\). Then \(\chi^{\prime \prime}(G) \leq 8\). As an immediate consequence of the above result, we get: Corollary: Let \(G\) be a planar graph with maximum degree \(\Delta(G)=6\) and without 3 -cycles. Then \(\chi^{\prime \prime}(G) \leq 8\).