Large chromatic number and Ramsey graphs

2011/03/21 by Biró, Csaba, Füredi, Zoltán, Jahanbekam, Sogol
#05C35 #05C69 #05D10 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1103.3917

Abstract

Let Q(n,c) denote the minimum clique size an n-vertex graph can have if its chromatic number is c. Using Ramsey graphs we give an exact, albeit implicit, formula for the case c is at least (n+3)/2.

Related

• Ramsey numbers and the size of graphs
• Three early problems on size Ramsey numbers
• An improved method for recursively computing upper bounds for two-colour\n Ramsey numbers
• On bounded degree graphs with large size-Ramsey numbers
• On the size-Ramsey number of hypergraphs