Reuniting χ-boundedness with polynomial χ-boundedness
Journal of Combinatorial Theory, Series B · 2026-01 · 176 · 30-73
DOI: 10.1016/j.jctb.2025.08.002 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Combinatorial Theory, Series B, 2026-01. Verfasst von Maria Chudnovsky und 3 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 55 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation, Air Force Office of Scientific Research, Institute for Basic Science.
Abstract (Originalsprache)
A class $\mathcal{F}$ of graphs is $\chi$-bounded if there is a function $f$ such that $\chi(H)\le f(\omega(H))$ for all induced subgraphs $H$ of a graph in $\mathcal{F}$. If $f$ can be chosen to be a polynomial, we say that $\mathcal{F}$ is polynomially $\chi$-bounded. Esperet proposed a conjecture that every $\chi$-bounded class of graphs is polynomially $\chi$-bounded. This conjecture has been disproved; it has been shown that there are classes of graphs that are $\chi$-bounded but not polynomially $\chi$-bounded. Nevertheless, inspired by Esperet's conjecture, we introduce Pollyanna classes of graphs. A class $\mathcal{C}$ of graphs is Pollyanna if $\mathcal{C}\cap \mathcal{F}$ is polynomially $\chi$-bounded for every $\chi$-bounded class $\mathcal{F}$ of graphs. We prove that several classes of graphs are Pollyanna and also present some proper classes of graphs that are not Pollyanna.
Förderung
- National Science Foundation
- Air Force Office of Scientific Research
- Institute for Basic Science
- EU Framework Programme for Research and Innovation Marie Skłodowska-Curie Actions
- Engineering and Physical Sciences Research Council
- Ministerie van Onderwijs, Cultuur en Wetenschap
- Dutch Research Council
- US Air Force
Zitieren
APA
Chudnovsky, M., Cook, L., Davies, J., & Oum, S. (2026). Reuniting χ-boundedness with polynomial χ-boundedness. Journal of Combinatorial Theory, Series B, 176, 30-73. https://doi.org/10.1016/j.jctb.2025.08.002
Vancouver
Chudnovsky M, Cook L, Davies J, Oum S. Reuniting χ-boundedness with polynomial χ-boundedness. Journal of Combinatorial Theory, Series B. 2026;176:30-73. doi:10.1016/j.jctb.2025.08.002
BibTeX
@article{Chudnovsky2026,
author = {Chudnovsky, Maria and Cook, Linda and Davies, James and Oum, Sang-il},
title = {Reuniting χ-boundedness with polynomial χ-boundedness},
journal = {Journal of Combinatorial Theory, Series B},
year = {2026},
volume = {176},
pages = {30--73},
doi = {10.1016/j.jctb.2025.08.002}
}
EUVIMED