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

DOI10.1007/S00373-022-02572-1MaRDI QIDQ2084788zbMATH OpenOpenAlexFDO

Authors Hoang La

Publication date 13 October 2022

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.01684

zbMATH Keywords

2-distance coloringdischarging methodsparse graphssquare coloring

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

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 $(Delta+3)$-coloring for graphs with maximum average degree less than $frac83$ and maximum degree $Deltageq4$ as well as graphs with maximum average degree less than $frac145$ and maximum degree $Deltageq6$.

Recommendations

• The list 2-distance coloring of sparse graphs
• 2-distance coloring of sparse graphs
• Graphs with maximum degree 17 and maximum average degree less than 3 are list 2-distance ( +2)-colorable
• 2-distance coloring of sparse graphs
• The list 2-distance coloring of a graph with (G)=5

Cites work

• \(r\)-hued \((r+1)\)-coloring of planar graphs with girth at least 8 for \(r\geq 9\)
• Coloring the square of a \(K_{4}\)-minor free graph
• scientific article; zbMATH DE number 3265667 (Why is no real title available?)
• scientific article; zbMATH DE number 3308991 (Why is no real title available?)
• List Colouring Squares of Planar Graphs
• List-coloring the square of a subcubic graph
• The list 2-distance coloring of a graph with (G)=5
• The square of a planar cubic graph is 7-colorable

Cited in

(15)

• List-recoloring of sparse graphs
• Distance-two coloring of sparse graphs
• (2+ )-nonrepetitive list colouring of paths
• 2-distance coloring of sparse graphs
• Graphs with maximum degree 17 and maximum average degree less than 3 are list 2-distance ( +2)-colorable
• scientific article; zbMATH DE number 6135423 (Why is no real title available?)
• The list 2-distance coloring of a graph with (G)=5
• 2-distance, injective, and exact square list-coloring of planar graphs with maximum degree 4
• 2-distance coloring of sparse graphs
• Some results on 2-distance coloring of planar graphs with girth five
• 2-distance \((\Delta + 1)\)-coloring of sparse graphs using the potential method
• On odd and strong odd colorings of graphs
• On 2-distance ( + 4)-coloring of planar graphs with girth five
• Strong odd coloring of sparse graphs
• The list 2-distance coloring of sparse graphs

This page was built for publication: 2-distance list \((\varDelta +3)\)-coloring of sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2084788)