Autor(es)

Jimenez, A. ; Knauer, K. ; Lintzmayer, C. N. ; Matamala, M. ; Pena, J. P. ; Quiroz, D. A. ; Sambinelli, M. ; Wakabayashi, Y. ; Yu, W. ; Zamora, J.

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE MATHEMATICS; v. 349, n. 2, p. 16-pg., 2026-02-01.

Resumo

The proper conflict-free chromatic number, chi 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 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 chi(G) <= chi o(G) <= chi pcf(G). We say that a graph class G is chi pcf-bounded (chi o-bounded) if there is a function f such that chi pcf(G) <= f(chi(G)) (chi o(G) <= f(chi(G))) for every G is an element of G. Caro, Petrusevski, and Skrekovski (2023) asked for classes that are linearly chi pcf-bounded (chi o-bounded) and, as a starting point, they showed that every claw-free graph G satisfies chi pcf(G) <= 2 Delta(G) + 1, which implies chi pcf(G) <= 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 pcf(G) <= Delta(G) + 6, and even chi pcf(G) <= Delta(G) + 4 if it is a quasi-line graph. These results also give further evidence to a conjecture by Caro, Petrusevski, and Skrekovski. Moreover, we show that convex-round graphs and permutation graphs are linearly chi pcf-bounded. For these last two results, we prove a lemma that reduces the problem of deciding if a hereditary class is linearly chi pcf-bounded to deciding if the bipartite graphs in the class are chi 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 pcf-bounded, while convex bipartite graphs are not even chi o-bounded, and we exhibit a class of bipartite circle graphs that is linearly chi o-bounded but not chi pcf-bounded. (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies. (AU)

• Processo FAPESP: 23/03167-5 - Combinatória clássica, assintótica, quântica e geométrica
• Beneficiário: Yoshiharu Kohayakawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 19/13364-7 - Problemas extremais e estruturais em teoria dos grafos
• Beneficiário: Cristina Gomes Fernandes
• Modalidade de apoio: Auxílio à Pesquisa - Regular