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

DOI10.1016/J.DISC.2015.11.012MaRDI QIDQ906469zbMATH OpenOpenAlexFDO

Authors Seog-Jin Kim, Boram Park

Publication date 21 January 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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$.

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

Cites work

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

Cited in

(6)

• On coloring numbers of graph powers
• Upper bound on chromatic number of square graph of sparse graphs
• Cliques in squares of graphs with maximum average degree less than 4
• Coloring the square of a sparse graph \(G\) with almost \(\varDelta(G)\) colors
• Coloring squares of graphs with mad constraints
• 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)