Coloring the square of graphs whose maximum average degree is less than 4

详细信息    查看全文

• 作者：Seog-Jin Kim^a ; ^{skim12@konkuk.ac.kr" class="auth_mail" title="E-mail the corresponding author} ; Boram Park^b ; ^{borampark@ajou.ac.kr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Coloring ; Square coloring ; Maximum average degree
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 April 2016
• 年：2016
• 卷：339
• 期：4
• 页码：1251-1260
• 全文大小：425 K

文摘

The square X15004112&_mathId=si2.gif&_user=111111111&_pii=S0012365X15004112&_rdoc=1&_issn=0012365X&md5=d22decdd0f6eda28d388567e84e7a543" title="Click to view the MathML source">G²$G^2$ of a graph G$G$ is the graph defined on 15e901" title="Click to view the MathML source">V(G)$V\left(G\right)$ such that two vertices u$u$ and v$v$ are adjacent in G²$G^2$ if the distance between u$u$ and v$v$ in G$G$ is at most 2. The maximum average degree   of G$G$, mad(G)$mad\left(G\right)$, is the maximum among the average degrees of the subgraphs of G$G$.

It is known in Bonamy et al. (2014) that there is no constant C$C$ such that every graph G$G$ with mad(G)<4$mad\left(G\right)<4$ has χ(G²)≤Δ(G)+C$\chi \left(G^2\right)\le \Delta \left(G\right)+C$. Charpentier (2014) conjectured that there exists an integer D$D$ such that every graph G$G$ with Δ(G)≥D$\Delta \left(G\right)\ge D$ and mad(G)<4$mad\left(G\right)<4$ has χ(G²)≤2Δ(G)$\chi \left(G^2\right)\le 2\Delta \left(G\right)$. Recent result in Bonamy et al. (2014) [2] implies that χ(G²)≤2Δ(G)$\chi \left(G^2\right)\le 2\Delta \left(G\right)$ if $mad\left(G\right)<4-\frac{1}{c}$ with Δ(G)≥40c−16$\Delta \left(G\right)\ge 40c-16$.

In this paper, we show for an integer c≥2$c\ge 2$, if $mad\left(G\right)<4-\frac{1}{c}$ and Δ(G)≥14c−7$\Delta \left(G\right)\ge 14c-7$, then χ_ℓ(G²)≤2Δ(G)${\chi }_{\ell }\left(G^2\right)\le 2\Delta \left(G\right)$, which improves the result in Bonamy et al. (2014) [2]. We also show that for every integer D$D$, there is a graph G$G$ with Δ(G)≥D$\Delta \left(G\right)\ge D$ such that mad(G)<4$mad\left(G\right)<4$, and χ(G²)=2Δ(G)+2$\chi \left(G^2\right)=2\Delta \left(G\right)+2$, which disproves Charpentier’s conjecture. In addition, we give counterexamples to Charpentier’s another conjecture in Charpentier (2014), stating that for every integer k≥3$k\ge 3$, there is an integer D_k$D_k$ such that every graph G$G$ with mad(G)<2k$mad\left(G\right)<2k$ and Δ(G)≥D_k$\Delta \left(G\right)\ge D_k$ has χ(G²)≤kΔ(G)−k$\chi \left(G^2\right)\le k\Delta \left(G\right)-k$.