Coloring squares of graphs with mad constraints
read the original abstract
A proper vertex $k$-coloring of a graph $G=(V,E)$ is an assignment $c:V\to \{1,2,\ldots,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) \geqslant 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)\geqslant \frac{5\Delta(G)}{2}$, improving the result of Kim and Park.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Coloring, List Coloring, and Painting Squares of Graphs (and other related problems)
This is a survey compiling results on strong edge-coloring and related coloring problems for squares of graphs in planar and sparse classes.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.