$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 Accéder directement au contenu
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

Paternité - Pas d'utilisation commerciale

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⟩
59 Consultations
20 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More