A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number

Abstract

We prove that for every $n$, there is a graph $G$ with $\chi (G)\ge n$ and $\omega (G)\le 3$ such that every induced subgraph $H$ of $G$ with $\omega (H)\le 2$ satisfies $\chi (H)\le 4$. This disproves a well-known conjecture. Our construction is a digraph with bounded clique number, large dichromatic number, and no induced directed cycles of odd length at least 5.

Accepted manuscript, see DOI for journal version

Cited by in corpus (1)

• Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of $P_4$