Bipartite induced density in triangle-free graphs (Q2185224)

Summary: We prove that any triangle-free graph on \(n\) vertices with minimum degree at least \(d\) contains a bipartite induced subgraph of minimum degree at least \(d^2/(2n)\). This is sharp up to a logarithmic factor in \(n\). Relatedly, we show that the fractional chromatic number of any such triangle-free graph is at most the minimum of \(n/d\) and \((2+o(1))\sqrt{n/\log n}\) as \(n\to\infty \). This is sharp up to constant factors. Similarly, we show that the list chromatic number of any such triangle-free graph is at most \(O(\min\{\sqrt{n},(n\log n)/d\})\) as \(n\to\infty \). Relatedly, we also make two conjectures. First, any triangle-free graph on \(n\) vertices has fractional chromatic number at most \((\sqrt{2}+o(1))\sqrt{n/\log n}\) as \(n\to\infty \). Second, any triangle-free graph on \(n\) vertices has list chromatic number at most \(O(\sqrt{n/\log n})\) as \(n\to\infty \).