Coloring the square of a sparse graph \(G\) with almost \(\varDelta(G)\) colors

DOI10.1016/j.dam.2016.06.012zbMath1346.05087arXiv1502.03132OpenAlexW2963647509MaRDI QIDQ317434

Matthew P. Yancey

Publication date: 30 September 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

sparse graphs2-distance coloringsquare coloring

Mathematics Subject Classification ID

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

Related Items

Graph \(r\)-hued colorings -- a survey, An introduction to the discharging method via graph coloring

Cites Work

• List coloring the square of sparse graphs with large degree
• Sufficient sparseness conditions for \(G^2\) to be \((\Delta + 1)\)-choosable, when \(\Delta \geq 5\)
• Coloring the square of graphs whose maximum average degree is less than 4
• 2-distance \((\varDelta +2)\)-coloring of planar graphs with girth six and \(\varDelta \geq 18\)
• Planar graphs of girth at least five are square \((\delta + 2)\)-choosable
• An optimal square coloring of planar graphs
• \(L(p,q)\)-labeling of sparse graphs
• Coloring squares of planar graphs with girth six
• A bound on the chromatic number of the square of a planar graph
• Sufficient conditions for planar graphs to be 2-distance (\(\Delta+1\))-colourable
• 2-distance coloring of sparse planar graphs
• 2-Distance Coloring of Sparse Graphs
• Labeling Planar Graphs with Conditions on Girth and Distance Two
• Counterexamples to the List Square Coloring Conjecture
• What Color Is Your Jacobian? Graph Coloring for Computing Derivatives
• Choosability conjectures and multicircuits