Chromatic number and mimimum degree of K_r-free graphs

2010/01/13 by Nikiforov, Vladimir · 4 citations
#05C35 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1001.2070

Abstract

A number of famous results about triangle-free graphs determine the maximum chromatic number of graphs of order n with minimum degree greater than n/3. In this note these results are extended to Kr-free graphs.

Cited by

• Edge density and minimum degree thresholds for H-free graphs with unbounded chromatic number
• A directed Andrásfai-Erdős-Sós theorem and chromatic profiles of oriented cycles
• Strong spectral stabilities for C_2k+1-free graphs
• Stability with minuscule structure for chromatic thresholds

Related

• A Brooks' Theorem for Triangle-Free Graphs
• Improvement on Brook theorem for (3 Times K1)-free Graphs
• On minimal triangle-free planar graphs with prescribed 1-defective chromatic number
• Improvement on Brook theorem for 2K2-free Graphs
• The list chromatic number of graphs with small clique number