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 language | English (US) |
|---|---|
| Pages (from-to) | 30-73 |
| Number of pages | 44 |
| Journal | Journal of Combinatorial Theory. Series B |
| Volume | 176 |
| DOIs | |
| State | Published - 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