Local structures in plane maps and distance colourings (Q5959100)

A plane map is called a normal plane map if the involved pseudograph is connected and all vertices and all faces have degree not less than three. The first purpose of the paper is to present a structural result on normal plane maps, which strengthens the one obtained by \textit{O. V. Borodin} in [Diskretn. Mat. 3, No. 4, 24-27 (1991; Zbl 0742.05034)] (strictly related to Kotzig's and Lebesgue's classical results). Then, the authors take into account the notion of \(t\)-distance chromatic number introduced by \textit{F. Kramer} and \textit{H. Kramer} in [C. R. Acad. Sci., Paris, Sér. A 268, 46-48 (1969; Zbl 0165.57302) and Ann. Discrete Math. 30, 275-284 (1986; Zbl 0601.05020)], and recently investigated in [\textit{Z. Skupień}, Discuss. Math., Graph Theory 15, No. 1, 89-106 (1995; Zbl 0833.05036)] and [\textit{G. Chen, A. Gyárfás}, and \textit{R. H. Schelp}, Discrete Math. 191, No. 1-3, 65-82 (1998; Zbl 0958.05053)]. The present paper yields a polynomial \(\Phi_t(D)\) in \(D\) of degree \(t-1\), such that the \(t\)-distance chromatic number of any planar graph \(G\) with maximum degree \(\Delta(G) \leq D\), where \(D \geq 8\), is bounded above by \(\Phi_t(D).\)