Coloring the square of a sparse graph with almost colors

详细信息    查看全文

• 作者：Matthew P. Yancey ^{mpyance@super.org" class="auth_mail" title="E-mail the corresponding author}
• 关键词：2-distance coloring ; Square coloring ; Sparse graphs
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：11 December 2016
• 年：2016
• 卷：214
• 期：Complete
• 页码：211-215
• 全文大小：379 K

文摘

For a graph abf0c793" title="Click to view the MathML source">G$G$, let G²$G^2$ be the graph with the same vertex set as abf0c793" title="Click to view the MathML source">G$G$ and xy∈E(G²)$xy\in E\left(G^2\right)$ when x≠y$x\ne y$ and d_G(x,y)≤2$d_G(x,y)\le 2$. Bonamy, Lévêque, and Pinlou conjectured that if $mad\left(G\right)<4-\frac{2}{c+1}$ and bf36f1eb1d32aa2" title="Click to view the MathML source">Δ(G)$\Delta \left(G\right)$ is large, then χ_ℓ(G²)≤Δ(G)+c${\chi }_{\ell }\left(G^2\right)\le \Delta \left(G\right)+c$. We prove that if c≥3$c\ge 3$, $mad\left(G\right)<4-\frac{4}{c+1}$, and bf36f1eb1d32aa2" title="Click to view the MathML source">Δ(G)$\Delta \left(G\right)$ is large, then χ_ℓ(G²)≤Δ(G)+c${\chi }_{\ell }\left(G^2\right)\le \Delta \left(G\right)+c$. Dvořák, Král’, Nejedlý, and Škrekovski conjectured that χ(G²)≤Δ(G)+2$\chi \left(G^2\right)\le \Delta \left(G\right)+2$ when bf36f1eb1d32aa2" title="Click to view the MathML source">Δ(G)$\Delta \left(G\right)$ is large and abf0c793" title="Click to view the MathML source">G$G$ is planar with girth at least 5$5$; our result implies χ(G²)≤Δ(G)+6$\chi \left(G^2\right)\le \Delta \left(G\right)+6$.