$r$-hued ( r + 1 ) -coloring of planar graphs with girth at least 8 for $r$ ≥ 9 - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles European Journal of Combinatorics Year : 2021

$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.
Fichier principal
Vignette du fichier
S0195669820301402.pdf (707.78 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-03475125 , version 1 (17-10-2022)

Licence

Identifiers

Cite

Xuan Hoang La, Mickaël Montassier, Alexandre Pinlou, Petru Valicov. $r$-hued ( r + 1 ) -coloring of planar graphs with girth at least 8 for $r$ ≥ 9. European Journal of Combinatorics, 2021, 91, pp.#103219. ⟨10.1016/j.ejc.2020.103219⟩. ⟨lirmm-03475125⟩
73 View
33 Download

Altmetric

Share

More