(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
| CREATOR | Guillaume Aubian, Luis Kuffner |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 5 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-08736