Strongly common graphs with odd girth are cycles

2023/05/18 by Leo Versteegen, Versteegen, Leo
Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2305.10903

openalex publication_date 2023/05/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A graph H is called strongly common if for every coloring ϕ of K_n with two colors, the number of monochromatic copies of H is at least the number of monochromatic copies of H in a random coloring of K_n with the same density of color classes as ϕ. In this note we prove that if a graph has odd girth but is not a cycle, then it is not strongly common. This answers a question of Chen and Ma.

Related

• A property on monochromatic copies of graphs containing a triangle
• Off-Diagonal Commonality of Graphs via Entropy
• Towards characterizing locally common graphs
• Common graphs with arbitrary connectivity and chromatic number
• Common graphs with arbitrary chromatic number