Boundedness for proper conflict-free and odd colorings.

Abstract

The proper conflict-free chromatic number, $\chi_{\mathrm{pcf}}(G)$, of a graph $G$ is the least positive integer $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, $\chi_{\mathrm{o}}(G)$, of $G$ is the least positive integer $k$ such that $G$ has a proper coloring in which for every nonisolated vertex there is a color appearing an odd number of times among its neighbors. We clearly have $\chi(G) \leq \chi_0(G) \leq \chi_{\mathrm{pcf}}(G)$. We say that a graph class $\mathcal{G}$ is $\chi_{\mathrm{pcf}}$-bounded ( $\chi_{\mathrm{o}}$ bounded) if there is a function $f$ such that $\chi_{\mathrm{pcf}}(G) \leq f(\chi(G))\left(\chi_{\mathrm{o}}(G) \leq f(\chi(G))\right)$ for every $G \in \mathcal{G}$. Caro, Petruševski, and Škrekovski (2023) asked for classes that are linearly $\chi_{\mathrm{pcf}}$ bounded ( $\chi_{\mathrm{o}}$-bounded) and, as a starting point, they showed that every claw-free graph $G$ satisfies $\chi_{\text {pcf }}(G) \leq 2 \Delta(G)+1$, which implies $\chi_{\text {pcf }}(G) \leq 4 \chi(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 $\chi_{\text {pcf }}(G) \leq \Delta(G)+6$, and even $\chi_{\text {pcf }}(G) \leq \Delta(G)+4$ if it is a quasi-line graph. These results also give further evidence to a conjecture by Caro, Petruševski, and Škrekovski. Moreover, we show that convex-round graphs and permutation graphs are linearly $\chi_{\text {pcf }}$-bounded. For these last two results, we prove a lemma that reduces the problem of deciding if a hereditary class is linearly $\chi_{\text {pcf }}$-bounded to deciding if the bipartite graphs in the class are $\chi_{\mathrm{pcf}}$-bounded by an absolute constant. This lemma complements a theorem of Liu (2024) and motivates us to further study boundedness in bipartite graphs. Among other results, we show that biconvex bipartite graphs are $\chi_{\text {pcf }}$ bounded, while convex bipartite graphs are not even $\chi_{\mathrm{o}}$-bounded, and we exhibit a class of bipartite circle graphs that is linearly $\chi_{\mathrm{o}}$-bounded but not $\chi_{\text {pcf }}$-bounded.