Strongly common graphs with odd girth are cycles
Reviewed by Pithpith:JPRBNC3Uopen to challenge →
classification
math.CO
keywords
commonstronglycoloringcopiesgirthgraphmonochromaticnumber
read the original abstract
A graph $H$ is called strongly common if for every coloring $\phi$ 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 $\phi$. 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.