Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 56 min ago
PreprintarXiv licencearXiv

Optimal Kt-free list colorings and the Pollyanna property of graphs with no triangular wheel

  • Hongyang Wang
  • Rong Wu
Open at sourcePDFDOICite

Abstract

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∈cal T and every integer t≥3, the Kt-free chromatic and choice numbers both equal ⌈ω(G)/(t−1)⌉. We further prove that cal T is k-strongly linear-Pollyanna for every integer k≥2, 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.

Related

  1. Cayley graphs of abelian groups, circular colorings and discrete fundamental groups
    Kengo Enami, Takahiro Matsushita
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  2. On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
    Mohammed Lalou, Nader Mbarek, Abdallah Skender +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Sequence b-colorings in graphs
    Marko Jakovac, Michael S. Lang
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Total eight-colorings of maximal planar graphs of maximum degree six
    Enqiang Zhu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Rich-neighbor 5-edge-colorings of subcubic graphs whose 3-vertices induce a matching
    Jiangxu Kong, Zhuming Lin, Yan Wang
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{wang2026optimal,
  title = {{Optimal $K_t$-free list colorings and the Pollyanna property of graphs with no triangular wheel}},
  author = {Hongyang Wang and Rong Wu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.35225},
  eprint = {2610.35225},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.35225},
}
RIS
TY  - UNPB
TI  - Optimal K_t-free list colorings and the Pollyanna property of graphs with no triangular wheel
AU  - Hongyang Wang
AU  - Rong Wu
PY  - 2026
DA  - 2026/10/26
PB  - arXiv
DO  - 10.48550/arxiv.2610.35225
UR  - https://arxiv.org/abs/2610.35225
AB  - 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∈cal T and every integer t≥3, the K_t-free chromatic and choice numbers both equal ⌈ω(G)/(t−1)⌉. We further prove that cal T is k-strongly linear-Pollyanna for every integer k≥2, 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.
ER  -