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 $\ddot{I}‡(G)\ge n$ and $\ddot{I}‰(G)\le 3$ such that every induced subgraph $H$ of $G$ with $\ddot{I}‰(H)\le 2$ satisfies $\ddot{I}‡(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