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

DOI10.1016/J.DISC.2015.11.012zbMATH Open1329.05112arXiv1506.04401OpenAlexW584708941MaRDI QIDQ906469FDOQ906469

Authors: Seog-Jin Kim, Boram Park 

Publication date: 21 January 2016

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

Abstract: The square $G^2$ of a graph $G$ is the graph defined on $V(G)$ such that two vertices $u$ and $v$ are adjacent in $G^2$ if the distance between $u$ and $v$ in $G$ is at most 2. The {em maximum average degree} of $G$, $mad(G)$, is the maximum among the average degrees of the subgraphs of $G$. It is known in cite{BLP-14-JGT} that there is no constant $C$ such that every graph $G$ with $mad(G)<4$ has $chi(G^2)leqDelta(G)+C$. Charpentier cite{Charpentier14} conjectured that there exists an integer $D$ such that every graph $G$ with $Delta(G)geD$ and $mad(G)<4$ has $chi(G^2)leq2Delta(G)$. Recent result in cite{BLP-DM} implies that $chi(G^2)leq2Delta(G)$ if $mad(G)<4-frac1c$ with $Delta(G)geq40c-16$. In this paper, we show for $cge2$, if $mad(G)<4-frac1c$ and $Delta(G)geq14c-7$, then $ch{i}_{e}ll(G^2)leq2Delta(G)$, which improves the result in cite{BLP-DM}. We also show that for every integer $D$, there is a graph $G$ with $Delta(G)geD$ such that $mad(G)<4$, and $chi(G^2)geq2Delta(G)+2$, which disproves Charpentier's conjecture. In addition, we give counterexamples to Charpentier's another conjecture in cite{Charpentier14}, stating that for every integer $kge3$, there is an integer $D_k$ such that every graph $G$ with $mad(G)<2k$ and $Delta(G)ge{D}_k$ has $chi(G^2)leqkDelta(G)-k$.

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

Recommendations

• Coloring squares of graphs with mad constraints
• Coloring the square of a sparse graph \(G\) with almost \(\varDelta(G)\) colors
• Upper bound on chromatic number of square graph of sparse graphs
• List coloring the square of sparse graphs with large degree
• Improved square coloring of planar graphs

zbMATH Keywords

coloringsquare coloringmaximum average degree

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• 2-distance \((\varDelta +2)\)-coloring of planar graphs with girth six and \(\varDelta \geq 18\)
• Coloring squares of planar graphs with girth six
• Labeling Planar Graphs with Conditions on Girth and Distance Two
• 2-Distance Coloring of Sparse Graphs
• List coloring the square of sparse graphs with large degree
• Graphs with maximum degree \(\varDelta\geq 17\) and maximum average degree less than 3 are list 2-distance \((\varDelta +2)\)-colorable

Cited In (5)

• Coloring squares of graphs with mad constraints
• On coloring numbers of graph powers
• Upper bound on chromatic number of square graph of sparse graphs
• Coloring the square of a sparse graph \(G\) with almost \(\varDelta(G)\) colors
• 3-dynamic coloring of planar triangulations

This page was built for publication: Coloring the square of graphs whose maximum average degree is less than 4

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