학술논문
A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number
Document Type
Working Paper
Source
Journal of Combinatorial Theory, Series B, Volume 158, Part 2, 2023, Pages 63-69
Subject
Language
Abstract
We prove that for every $n$, there is a graph $G$ with $\chi(G) \geq n$ and $\omega(G) \leq 3$ such that every induced subgraph $H$ of $G$ with $\omega(H) \leq 2$ satisfies $\chi(H) \leq 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.
Comment: Accepted manuscript, see DOI for journal version
Comment: Accepted manuscript, see DOI for journal version