Common graphs with arbitrary connectivity and chromatic number

2022/07/19 by Se-Jin Ko, Joonkyung Lee, Ko, Sejin +1
Computer Science · Mathematics · #05D10 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2207.09427

openalex publication_date 2022/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A graph H is common if the number of monochromatic copies of H in a 2-edge-colouring of the complete graph K_n is asymptotically minimised by the random colouring. We prove that, given k,r>0, there exists a k-connected common graph with chromatic number at least r. The result is built upon the recent breakthrough of Kráľ, Volec, and Wei who obtained common graphs with arbitrarily large chromatic number and answers a question of theirs.

Related

• Common graphs with arbitrary chromatic number
• Common Pairs of Graphs
• A property on monochromatic copies of graphs containing a triangle
• Towards characterizing locally common graphs
• On tripartite common graphs