(Claw, C → 3 \vec{C}_{3} )-free Digraphs with Unbounded Dichromatic Number

Guillaume Aubian, Luis Kuffner · 2026

Read (Claw, C → 3 \vec{C}_{3} )-free Digraphs with Unbounded Dichromatic Number by Guillaume Aubian, Luis Kuffner (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-08736.txt.

Description

Graph coloring questions often turn on whether a forbidden pattern forces a bound on coloring number. Guillaume Aubian and Luis Kuffner construct orientations of rook graphs that dodge one pattern yet break coloring bounds entirely. Their arXiv paper works with graphs whose underlying structure is claw-free.

The orientations contain no directed triangle, yet their dichromatic number grows without bound. That combination refutes a prior conjecture in the literature, and it sharpens an earlier result by Carbonero, Koerts, Moore, and Spirkl. Readers get a compact counterexample with a clear moral: forbidding directed triangles does not tame dichromatic number, even on claw-free ground.

Catalog record

CREATORGuillaume Aubian, Luis Kuffner
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE5 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-08736

Browse the full library · About the Tower of Babel