$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
Article Dans Une Revue European Journal of Combinatorics Année : 2021

$r$-hued ( r + 1 ) -coloring of planar graphs with girth at least 8 for $r$ ≥ 9

Résumé

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
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Licence

Identifiants

Citer

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⟩
79 Consultations
38 Téléchargements

Altmetric

Partager

More