Bipartite induced density in triangle-free graphs

Wouter Cames van Batenburg ; Rémi de Joannis de Verclos ; Ross J. Kang¹ ; François Pirot

¹Radboud University Nijmegen

The electronic journal of combinatorics, Tome 27 (2020) no. 2

Résumé

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$.

Détail

DOI : 10.37236/8650

Classification : 05C35, 05C15
Mots-clés : fractional chromatic number, list chromatic number