Total coloring of planar graphs without adjacent short cycles (Q512886): Difference between revisions

As well known, a total \(k\)-coloring of a graph \(G\) is a map \(c:V(G)\cup E(G)\rightarrow \{1,\ldots,k\}\) for which two adjacent or incident elements of \(V(G)\cup E(G)\) receive a different value, called color. The total chromatic number \(\chi^{\prime\prime}(G)\) is then the minimum integer \(k\) for which there exists a total \(k\)-coloring. A natural lower bound for this invariant is \(\Delta(G)+1\leq \chi^{\prime\prime}(G)\) where \(\Delta(G)\) represents the maximum degree of \(G\). Two cycles are adjacent if they share at least one edge. The authors show in this work that the total chromatic number of planar graphs without short adjacent cycles and big enough maximum degree equals to the above mentioned lower bound. More precisely, if \(\Delta(G)\geq 8\) and there are no adjacent cycles of length at most seven, then \(\chi^{\prime\prime}(G)=\Delta(G)+1\).