Brooks-type theorems for relaxations of square colorings

arXiv2302.06125MaRDI QIDQ6508799FDOQ6508799

Authors: Eun-Kyung Cho, Ilkyoo Choi, Hyemin Kwon, Boram Park 

Abstract: The following relaxation of proper coloring the square of a graph was recently introduced: for a positive integer $h$, the {it proper $h$-conflict-free chromatic number} of a graph $G$, denoted $ch{i}_{pcf}^h(G)$, is the minimum $k$ such that $G$ has a proper $k$-coloring where every vertex $v$ has $minde{g}_G(v),h$ colors appearing exactly once on its neighborhood. Caro, Petruv{s}evski, and v{S}krekovski put forth a Brooks-type conjecture: if $G$ is a graph with $Delta(G)ge3$, then $ch{i}_{pcf}^1(G)leqDelta(G)+1$. The best known result regarding the conjecture is $ch{i}_{pcf}^1(G)leq2Delta(G)+1$, which is implied by a result of Pach and Tardos. We improve upon the aforementioned result for all $h$, and also enlarge the class of graphs for which the conjecture is known to be true. Our main result is the following: for a graph $G$, if $Delta(G)geh+2$, then $ch{i}_{pcf}^h(G)le(h+1)Delta(G)-1$; this is tight up to the additive term as we explicitly construct infinitely many graphs $G$ with $ch{i}_{pcf}^h(G)=(h+1)(Delta(G)-1)$. We also show that the conjecture is true for chordal graphs, and obtain partial results for quasi-line graphs and claw-free graphs. Our main result also improves upon a Brooks-type result for $h$-dynamic coloring.

This page was built for publication: Brooks-type theorems for relaxations of square colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6508799)