2-distance list (Δ+ 3)-coloring of sparse graphs

2021/05/04 by Hoang La, La, Hoang · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.2105.01684

7 pages. arXiv admin note: text overlap with arXiv:2103.11687

arxiv created 2021/05/04 · arxiv updated 2021/05/06

Abstract

A 2-distance list k-coloring of a graph is a proper coloring of the vertices where each vertex has a list of at least k available colors and vertices at distance at most 2 cannot share the same color. We prove the existence of a 2-distance list (Δ+ 3)-coloring for graphs with maximum average degree less than \frac83 and maximum degree Δ≥ 4 as well as graphs with maximum average degree less than \frac145 and maximum degree Δ≥ 6.

Citations

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

Cited by

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

Related

• 2-distance (Δ+2)-coloring of sparse graphs
• 2-distance (Δ+1)-coloring of sparse graphs using the potential method
• Graphs with maximum degree D at least 17 and maximum average degree less than 3 are list 2-distance (D+2)-colorable
• 2-distance list (Δ+2)-coloring of planar graphs with girth at least 10
• 2-Distance Colorings of Integer Distance Graphs