Optimal $K_t$-free list colorings and the Pollyanna property of graphs with no triangular wheel
A wheel consists of an induced cycle of length at least four and a vertex with at least three neighbors on the cycle. Let $\cal T$ be the class of graphs with no wheel containing a triangle. We prove that, for every $G\in\cal T$ and every integer $t\ge3$, the $K_t$-free chromatic and choice numbers both equal $\lceil{ω(G)/(t-1)}\rceil$. We further prove that $\cal T$ is $k$-strongly linear-Pollyanna for every integer $k\ge2$, and hence is linear-Pollyanna. In particular, the class of wheel-free graphs is Pollyanna, answering Problem 10.2 of Chudnovsky, Cook, Davies and Oum.
Authors
- Rong Wu
- Hongyang Wang
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-10-26
- DOI
- https://doi.org/10.48550/arxiv.2610.35225
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint