EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Reuniting χ-boundedness with polynomial χ-boundedness

Maria Chudnovsky, Linda Cook, James Davies, Sang-il Oum

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →