Total chromatic number of regular graphs of odd order and high degree (Q1918537): Difference between revisions

The total chromatic number \(\chi_T(G)\) of a simple graph \(G=(V, E)\) is the least number of colors needed to color the edges and vertices of \(G\) so that no incident or adjacent elements receive the same color. A well-known total coloring conjecture says that \(\chi_T(G)\leq\Delta+2\), where \(\Delta\) is the maximum degree of graph \(G\). \textit{A. G. Chetwynd} et al. [J. Lond. Math. Soc., II. Ser. 44, No. 2, 193-202 (1991; Zbl 0753.05033)] proved that if \(G\) is \(\Delta\)-regular of odd order and \(\Delta\geq(\sqrt 7/3)|V|\), then \(\chi_T(G)= \Delta+1\) iff \(G\) is conformable, otherwise \(\chi_T(G) =\Delta +2\). The author of the paper improves slightly this result by showing that it is enough to require that \(\Delta \geq ((\sqrt{37}-1)/6) |V|\) for a \(\Delta\)-regular conformable graph \(G\) of odd order to have \(\chi_T(G) =\Delta+1\). Otherwise the total chromatic number \(\chi_T(G)\) equals \(\Delta+2\).