The rate of growth of the minimum clique size of graphs of given order and chromatic number

2012/10/01 by Csaba Bíró, Csaba Biró, Biró, Csaba +2
Computer Science · Mathematics · #05C15 (Primary) 05D10 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:05C15 #msc:05D10

paper · pdf · doi:10.48550/arxiv.1210.0412

openalex publication_date 2012/10/01 · arxiv created 2014/02/03 · arxiv updated 2014/02/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let Q(n,c) denote the minimum clique number over graphs with n vertices and chromatic number c. We determine the rate of growth of of the sequence Q(n,\lceil rn \rceil)_n=1^∞ for any fixed 0<r≤ 1. We also give a better upper bound for Q(n,\lceil rn \rceil).

Related

• On the growth rate of chromatic numbers of finite subgraphs
• Large chromatic number and Ramsey graphs
• The clique chromatic number of sparse random graphs
• Clique colouring of binomial random graphs
• Tight asymptotics of clique-chromatic numbers of dense random graphs