$r$-hued ( r + 1 ) -coloring of planar graphs with girth at least 8 for $r$ ≥ 9
Abstract
Let r,k ≥ 1 be two integers. An r-hued k-coloring of the vertices of a graph G = (V,E) is a proper k-coloring of the vertices, such that, for every vertex v ∈ V , the number of colors in its neighborhood is at least min{dG(v), r}, where dG(v) is the degree of v. We prove the existence of an r-hued (r+1)-coloring for planar graphs with girth at least 8 for r ≥ 9. As a corollary, every planar graph with maximum degree ∆ ≥ 9 and girth at least 8 admits a 2-distance (∆ + 1)-coloring.
Origin | Files produced by the author(s) |
---|