2-distance (Δ+1)-coloring of sparse graphs using the potential method - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2021

2-distance (Δ+1)-coloring of sparse graphs using the potential method

Xuan Hoang La
Mickaël Montassier

Résumé

A 2-distance k-coloring of a graph is a proper k-coloring of the vertices where vertices at distance at most 2 cannot share the same color. We prove the existence of a 2-distance (∆ + 1)-coloring for graphs with maximum average degree less than 18 and maximum degree ∆ ≥ 7. As a corollary, every planar graph with 7 girth at least 9 and ∆ ≥ 7 admits a 2-distance (∆ + 1)-coloring. The proof uses the potential method to reduce new configurations compared to classic approaches on 2-distance coloring.

Dates et versions

lirmm-04042407 , version 1 (23-03-2023)

Identifiants

Citer

Xuan Hoang La, Mickaël Montassier. 2-distance (Δ+1)-coloring of sparse graphs using the potential method. 2021. ⟨lirmm-04042407⟩
5 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More