Boundedness for proper conflict-free and odd colorings

Andrea JimÃ©nez; Andrea Jiménez; Kolja Knauer; Carla Negri Lintzmayer; MartÃ­n Matamala; Martín Matamala; Juan Pablo PeÃ±a; Juan Pablo Peña; Daniel A. Quiroz; Maycon Sambinelli; Yoshiko Wakabayashi; Weiqiang Yu; José Zamora; JosÃ© Zamora

doi:10.1016/j.disc.2025.114730

paper

Boundedness for proper conflict-free and odd colorings

arXiv:2308.00170 · doi:10.1016/j.disc.2025.114730

Abstract

The proper conflict-free chromatic number, $χ_{p c f} (G)$ , of a graph $G$ is the least $k$ such that $G$ has a proper $k$ -coloring in which for each non-isolated vertex there is a color appearing exactly once among its neighbors. The proper odd chromatic number, $χ_{o} (G)$ , of $G$ is the least $k$ such that $G$ has a proper coloring in which for every non-isolated vertex there is a color appearing an odd number of times among its neighbors. We say that a graph class $G$ is $χ_{p c f}$ -bounded ( $χ_{o}$ -bounded) if there is a function $f$ such that $χ_{p c f} (G) \leq f (χ (G))$ ( $χ_{o} (G) \leq f (χ (G))$ ) for every $G \in G$ . Caro et al. (2022) asked for classes that are linearly $χ_{p c f}$ -bounded ( $χ_{p c f}$ -bounded), and as a starting point, they showed that every claw-free graph $G$ satisfies $χ_{p c f} (G) \leq 2Δ (G) + 1$ , which implies $χ_{p c f} (G) \leq 4 χ (G) + 1$ . In this paper, we improve the bound for claw-free graphs to a nearly tight bound by showing that such a graph $G$ satisfies $χ_{p c f} (G) \leq Δ (G) + 6$ , and even $χ_{p c f} (G) \leq Δ (G) + 4$ if it is a quasi-line graph. These results also give evidence for a conjecture by Caro et al. Moreover, we show that convex-round graphs and permutation graphs are linearly $χ_{p c f}$ -bounded. For these last two results, we prove a lemma that reduces the problem of deciding if a hereditary class is linearly $χ_{p c f}$ -bounded to deciding if the bipartite graphs in the class are $χ_{p c f}$ -bounded by an absolute constant. This lemma complements a theorem of Liu (2022) and motivates us to study boundedness in bipartite graphs. In particular, we show that biconvex bipartite graphs are $χ_{p c f}$ -bounded while convex bipartite graphs are not even $χ_{o}$ -bounded, and exhibit a class of bipartite circle graphs that is linearly $χ_{o}$ -bounded but not $χ_{p c f}$ -bounded.

26 pages, 1 figure. Slight changes according to reviewers' comments. Proof of Lemma 1.3 expanded for clarity