Reuniting χ-boundedness with polynomial χ-boundedness

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

Research output: Contribution to journalArticlepeer-review

Abstract

A class F of graphs is χ-bounded if there is a function f such that χ(H)≤f(ω(H)) for all induced subgraphs H of a graph in F. If f can be chosen to be a polynomial, we say that F is polynomially χ-bounded. Esperet proposed a conjecture that every χ-bounded class of graphs is polynomially χ-bounded. This conjecture has been disproved; it has been shown that there are classes of graphs that are χ-bounded but not polynomially χ-bounded. Nevertheless, inspired by Esperet's conjecture, we introduce Pollyanna classes of graphs. A class C of graphs is Pollyanna if C∩F is polynomially χ-bounded for every χ-bounded class F of graphs. We prove that several classes of graphs are Pollyanna and also present some proper classes of graphs that are not Pollyanna.

Original languageEnglish (US)
Pages (from-to)30-73
Number of pages44
JournalJournal of Combinatorial Theory. Series B
Volume176
DOIs
StatePublished - Jan 2026

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Bowtie-free graphs
  • Bull-free graphs
  • Chromatic number
  • Graph vertex coloring
  • χ-bounded class

Fingerprint

Dive into the research topics of 'Reuniting χ-boundedness with polynomial χ-boundedness'. Together they form a unique fingerprint.

Cite this