Boundedness for proper conflict-free and odd colorings

The proper conflict-free chromatic number, χ_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, χ_o(G), of G is the least positive integer 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 clearly have χ(G)≤χ_o(G)≤χ_pcf(G). We say that a graph class G is χ_pcf-bounded (χ_o-bounded) if there is a function f such that χ_pcf(G)≤f(χ(G)) (χ_o(G)≤f(χ(G))) for every G∈G. Caro, Petruševski, and Škrekovski (2023) asked for classes that are linearly χ_pcf-bounded (χ_o-bounded) and, as a starting point, they showed that every claw-free graph G satisfies χ_pcf(G)≤2Δ(G)+1, which implies χ_pcf(G)≤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 χ_pcf(G)≤Δ(G)+6, and even χ_pcf(G)≤Δ(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 χ_pcf-bounded. For these last two results, we prove a lemma that reduces the problem of deciding if a hereditary class is linearly χ_pcf-bounded to deciding if the bipartite graphs in the class are χ_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 χ_pcf-bounded, while convex bipartite graphs are not even χ_o-bounded, and we exhibit a class of bipartite circle graphs that is linearly χ_o-bounded but not χ_pcf-bounded.