2018/08/07 by van Batenburg, Wouter Cames, de Verclos, Rémi de Joannis, Kang, Ross J. +1
#05C15 #05C35 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1808.02512
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 d2/(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))√(n/log n) as n→∞. 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\√(n),(nlog n)/d\) as n→∞. Relatedly, we also make two conjectures. First, any triangle-free graph on n vertices has fractional chromatic number at most (√(2)+o(1))√(n/log n) as n→∞. Second, any triangle-free graph on n vertices has list chromatic number at most O(√(n/log n)) as n→∞.