Coloring squares of graphs with mad constraints

Abstract

A proper vertex $k$-coloring of a graph $G=(V,E)$ is an assignment $c:V\to \{1,2,\dots ,k\}$ of colors to the vertices of the graph such that no two adjacent vertices are associated with the same color. The square $G^2$ of a graph $G$ is the graph defined by $V(G)=V(G^2)$ and $uv\in E(G^2)$ if and only if the distance between $u$ and $v$ is at most two. We denote by $\chi (G^2)$ the chromatic number of $G^2$, which is the least integer $k$ such that a $k$-coloring of $G^2$ exists. By definition, at least $\Delta (G)+1$ colors are needed for this goal, where $\Delta (G)$ denotes the maximum degree of the graph $G$. In this paper, we prove that the square of every graph $G$ with $\text{mad}(G)<4$ and $\Delta (G)⩾8$ is $(3\Delta (G)+1)$-choosable and even correspondence-colorable. Furthermore, we show a family of $2$-degenerate graphs $G$ with $\text{mad}(G)<4$, arbitrarily large maximum degree, and $\chi (G^2)⩾\frac{5\Delta (G)}{2}$, improving the result of Kim and Park.

14 pages, 4 figures