×

Sufficient conditions for the 2-distance \((\Delta+1)\)-colorability of planar graphs with girth 6. (Russian) Zbl 1249.05113

It is known that
(a)
\(\Delta+1\) is a lower bound for a 2-distance chromatic number of a graph \(G\) with maximum degree \(\Delta\);
(b)
if \(G\) is planar and its girth is at least 7 then, for sufficiently large \(\Delta\), this bound is attained;
(c)
statement (b) is not true for graphs with girth 6.
For a planar graph \(G\) with girth 6, \(\Delta\geq 179\), and every edge incident with a vertex of degree 1 or 2, the authors prove that the 2-distance chromatic number of \(G\) is equal to \(\Delta+1\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C12 Distance in graphs

Keywords:

cycle
PDFBibTeX XMLCite