Coloring t-perfect graphs with fewer colors

Abstract

Recently, Chudnovsky, Cook, Davies, Oum, and Tan obtained the first finite bound on the chromatic number of t-perfect graphs, showing that they are 199053-colorable. We improve this bound to 130 by refining their proof. The original proof establishes that every graph with large odd girth and large chromatic number contains a certain structure called an r-arithmetic rope, and that its existence in a certain leveling of a graph with large odd girth would imply an odd wheel as a t-minor, a known obstruction to t-perfectness. While their technique requires a lower bound on the chromatic number that is exponential in r, we show that the existence of an r-arithmetic rope can already be guaranteed under a linear bound. Using a slightly weakened notion of arithmetic ropes allows us to reduce the bound even further.

Coloring 3-colorable graphs with O(n^4/23) colors via a Gaussian-cover recursion
Emile Anand
arXiv1 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Dominated Coloring of Some Classes of Perfect and Unicyclic Graphs
Sneha R, J. Geetha, K. Somasundaram
arXiv26 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
On generalized token graphs with tokens of different colors
Cristina Dalfó, Blas Fernández, Miquel Àngel Fiol +1
arXiv5 Nov 2026PreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
Bounds for B-coloring planar and outerplanar graphs
Ryan Martin, Miklós Ruszinkó, Gábor Sárközy
Discrete Mathematics15 Sep 2026Peer-reviewedLicence not statedCombinatorics & discrete mathematicsHAL
COLORING SEMIMINIMAL CAYLEY GRAPHS
Ignacio Garc Ía-Marco, Kolja Knauer, Giuliamaria Menara
HAL3 Sep 2026PreprintCC BY 4.0Full textGeneral mathematicsHAL

Cite

BibTeX RIS

BibTeX

@misc{novakovic2026coloring,
  title = {{Coloring t-perfect graphs with fewer colors}},
  author = {Matija Novaković and Stefan Weltge},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2607.05961},
  eprint = {2607.05961},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.05961},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Coloring t-perfect graphs with fewer colors
AU  - Matija Novaković
AU  - Stefan Weltge
PY  - 2026
DA  - 2026/10/29
PB  - arXiv
DO  - 10.48550/arxiv.2607.05961
UR  - https://arxiv.org/abs/2607.05961
AB  - Recently, Chudnovsky, Cook, Davies, Oum, and Tan obtained the first finite bound on the chromatic number of t-perfect graphs, showing that they are 199053-colorable. We improve this bound to 130 by refining their proof. The original proof establishes that every graph with large odd girth and large chromatic number contains a certain structure called an r-arithmetic rope, and that its existence in a certain leveling of a graph with large odd girth would imply an odd wheel as a t-minor, a known obstruction to t-perfectness. While their technique requires a lower bound on the chromatic number that is exponential in r, we show that the existence of an r-arithmetic rope can already be guaranteed under a linear bound. Using a slightly weakened notion of arithmetic ropes allows us to reduce the bound even further.
ER  -

Abstract

Related

Cite