Journal of Combinatorics

Volume 2 (2011)

Number 1

Graphs containing triangles are not 3-common

Pages: 1 – 14



James Cummings (Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh Penn., U.S.A.)

Michael Young (Department of Mathematics, Iowa State University, Ames, Iowa, U.S.A.)


A finite graph $G$ is {\em $k$-common} if the minimum (over all $k$-colourings of the edges of $K_n$) of the number of monochromatic labelled copies of $G$ is asymptotically equal, as $n$ tends to infinity, to the expected number of such copies in a random $k$-colouring of the edges of $K_n$. Jagger, \u{S}\u{t}oví\u{c}ek and Thomason showed that graphs which contain $K_4$ are not $2$-common. We prove that graphs which contain $K_3$ are not $3$-common.

Published 15 June 2011