Total colourings of planar graphs with large girth

The total chromatic number \(X=X(G)\) of a graph \(G\) is the smallest number of colours that suffice to colour the vertices and edges of \(G\) so that no two adjacent or incident elements have the same colour. It is clear that \(X\geq \Delta+1\), and \textit{M. Behzad} [Doctoral Thesis, Michigan State University, 1965] and \textit{V. G. Vizing} [Usp. Mat. Nauk 23, No. 6(144), 117-134 (1968; Zbl 0177.52301 and Zbl 0192.60502)] conjectured that \(X\leq \Delta+2\), for every graph \(G\) with maximum degree \(\Delta\). For planar graphs with \(\Delta \geq 9\) the conjecture was verified by \textit{O. V. Borodin} [J. Reine Angew. Math. 394, 180-195 (1989; Zbl 0653.05029)]. In this paper the girth is involved into the the play. Recall that the girth of a graph is the length of its shortest cycle. Theorem: Let \(G\) be a planar graph with maximum degree \(\Delta\) and girth \(g\). Then \(X(G)=\Delta+1\) in each of the following cases: (a) \(\Delta \geq 11\); (b) \(\Delta \geq 7\) and \(g\geq 4\); (c) \(\Delta \geq 5\) and \(g\geq 5\); (d) \(\Delta\geq 4\) and \(g\geq 6\); (e) \(\Delta\geq 3\) and \(g\geq 10\). The cases (a) and (b) were proved by the same authors in previous papers. In the present paper the rest cases (c), (d) and (e) are proved. The results (c), (d) and (e) hold also for graphs in the projective plane, torus, and Klein bottle. The papers brings also a survey of previous results concerning the topic.

Recommendations

Cited in

(39)

This page was built for publication: Total colourings of planar graphs with large girth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1378290)