2-Distance list (Δ+2)-coloring of planar graphs with girth at least 10 - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Journal of Combinatorial Optimization Année : 2022

2-Distance list (Δ+2)-coloring of planar graphs with girth at least 10

Xuan Hoang La
Mickaël Montassier

Résumé

Given a graph G and a list assignment L(v) for each vertex of v of G. A proper L-list-coloring of G is a function that maps every vertex to a color in L(v) such that no pair of adjacent vertices have the same color. We say that a graph is list k-colorable when every vertex v has a list of colors of size at least k. A 2-distance coloring is a coloring where vertices at distance at most 2 cannot share the same color. We prove the existence of a 2-distance list (Δ+2)-coloring for planar graphs with girth at least 10 and maximum degree Δ≥4.
Fichier principal
Vignette du fichier
2109.14499.pdf (684.64 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-04041786 , version 1 (17-10-2023)

Identifiants

Citer

Xuan Hoang La, Mickaël Montassier. 2-Distance list (Δ+2)-coloring of planar graphs with girth at least 10. Journal of Combinatorial Optimization, 2022, 44 (2), pp.1356-1375. ⟨10.1007/s10878-022-00883-w⟩. ⟨lirmm-04041786⟩
39 Consultations
34 Téléchargements

Altmetric

Partager

More