Charpentier's coloring conjecture for squares of graphs with maximum average degree below 4

From papers

Let GG be a graph, let Δ(G)\Delta(G) denote its maximum degree, let mad(G)\operatorname{mad}(G) denote its maximum average degree, and let G2G^2 be its square, with chromatic number χ(G2)\chi(G^2). Charpentier's conjecture. There exists an integer DD such that every graph GG with Δ(G)D\Delta(G) \ge D and mad(G)<4\operatorname{mad}(G) < 4 has

χ(G2)2Δ(G).\chi(G^2) \le 2\Delta(G).

The conjecture was disproved by Kim and Park, who showed that for every positive integer DD there is a graph satisfying the stated degree and maximum-average-degree conditions with χ(G2)=2Δ(G)+2\chi(G^2)=2\Delta(G)+2.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

H. A. Kierstead, Daqing Yang and Junjun Yi, “On coloring numbers of graph powers”, arXiv:1907.10962 (2019).

Solutions 0

No solutions have been posted yet.