Acyclic subgraphs with high chromatic number

Abstract

For an oriented graph $G$, let $f(G)$ denote the maximum chromatic number of an acyclic subgraph of $G$. Let $f(n)$ be the smallest integer such that every oriented graph $G$ with chromatic number larger than $f(n)$ has $f(G)>n$. Let $g(n)$ be the smallest integer such that every tournament $G$ with more than $g(n)$ vertices has $f(G)>n$. It is straightforward that $\Omega (n)\le g(n)\le f(n)\le n^2$. This paper provides the first nontrivial lower and upper bounds for $g(n)$. In particular, it is proved that $\frac{1}{4}{n}^{8/7}\le g(n)\le n^2-(2-\frac{1}{\sqrt{2}})n+2$. It is also shown that $f(2)=3$, i.e. every orientation of a $4$-chromatic graph has a $3$-chromatic acyclic subgraph. Finally, it is shown that a random tournament $G$ with $n$ vertices has $f(G)=\Theta (\frac{n}{\log n})$ whp.

Cited by in corpus (2)

• Acyclic subgraphs of tournaments with high chromatic number
• Acyclic subgraphs of digraphs with high chromatic number