Bounded chromatic number of graphs with small clique number and large minimum degree
En palabras de los autores
We prove that every triangle-free graph with minimum degree at least is -colorable and thereby settle a problem of Brandt and Thomass\'e (2005) at the threshold . The number four is best possible. For a positive integer-valued function , we relate the chromatic number of -vertex subgraphs of the Kneser graph to that of triangle-free graphs with minimum degree at least . Consequently, for every and , and for all sufficiently large , every -vertex triangle-free graph with minimum degree at least has chromatic number at most . We also show that every sufficiently large -vertex maximal triangle-free graph with minimum degree at least and chromatic number at least contains a bipartite subgraph with parts of orders and ; the remaining induced subgraph admits a homomorphism to . Finally, we connect maximal -free graphs with minimum degree at least to -free graphs and extend these results to -free graphs. Our proofs employ the recent strong Brandt--Thomass\'{e} theorem of \L uczak, Polcyn, and Reiher.
Apareció: martes, 22 de septiembre. arXiv. Preprint, todavía sin revisión por pares.