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

DOI10.1016/J.DAM.2016.06.012zbMATH Open1346.05087arXiv1502.03132OpenAlexW2963647509MaRDI QIDQ317434FDOQ317434

Authors: Matthew Yancey 

Publication date: 30 September 2016

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

Abstract: For a graph $G$, let $G^2$ be the graph with the same vertex set as $G$ and $xyinE(G^2)$ when $xeqy$ and $d_G(x,y)leq2$. Bonamy, L'ev^{e}que, and Pinlou conjectured that if $mad(G)<4-frac2c+1$ and $Delta(G)$ is large, then $ch{i}_{e}ll(G^2)leqDelta(G)+c$. We prove that if $cgeq3$, $mad(G)<4-frac4c+1$, and $Delta(G)$ is large, then $ch{i}_{e}ll(G^2)leqDelta(G)+c$. Dvov{r}'ak, Kr'{a}soft{l}, Nejedl'{y}, and v{S}krekovski conjectured that $chi(G^2)leqDelta(G)+2$ when $Delta(G)$ is large and $G$ is planar with girth at least $5$; our result implies $chi(G^2)leqDelta(G)+6$.

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

Recommendations

• Upper bound on chromatic number of square graph of sparse graphs
• Coloring the square of graphs whose maximum average degree is less than 4
• Coloring squares of planar graphs with girth six
• Coloring squares of graphs with mad constraints
• Planar graphs of girth at least five are square \((\delta + 2)\)-choosable

zbMATH Keywords

sparse graphs2-distance coloringsquare coloring

Mathematics Subject Classification ID

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

Cites Work

• What Color Is Your Jacobian? Graph Coloring for Computing Derivatives
• 2-distance \((\varDelta +2)\)-coloring of planar graphs with girth six and \(\varDelta \geq 18\)
• 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
• Labeling Planar Graphs with Conditions on Girth and Distance Two
• Planar graphs of girth at least five are square \((\delta + 2)\)-choosable
• 2-Distance Coloring of Sparse Graphs
• Counterexamples to the list square coloring conjecture
• Choosability conjectures and multicircuits
• 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

Cited In (8)

• Painting squares in \(\Delta^2-1\) shades
• Coloring squares of graphs with mad constraints
• Upper bound on chromatic number of square graph of sparse graphs
• 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
• Graph \(r\)-hued colorings -- a survey
• Coloring squares of planar graphs with girth six
• An introduction to the discharging method via graph coloring

This page was built for publication: Coloring the square of a sparse graph \(G\) with almost \(\varDelta(G)\) colors

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