R-hued (r+1)-coloring of planar graphs with girth at least 8 for r≥9. (January 2021)

• Record Type: Journal Article
• Authors: La, Hoang; Montassier, Mickael; Pinlou, Alexandre; Valicov, Petru
• Is Part Of: European journal of combinatorics. Volume 91(2021)
• Publication Date: 2021-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2020.103219
• Languages: English
• ISSNs: 0195-6698

Abstract

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 { d G ( v ), r }, where d G ( 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.