pith. sign in

arxiv: 1902.08135 · v1 · pith:P7QDZU3Hnew · submitted 2019-02-21 · 🧮 math.CO

Coloring squares of graphs with mad constraints

classification 🧮 math.CO
keywords graphdeltacoloringcolorsdegreegeqslantgraphsleast
0
0 comments X
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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Coloring, List Coloring, and Painting Squares of Graphs (and other related problems)

    math.CO 2022-10 unverdicted

    This is a survey compiling results on strong edge-coloring and related coloring problems for squares of graphs in planar and sparse classes.