Contents Online

# Journal of Combinatorics

## Volume 2 (2011)

### Number 1

### Graphs containing triangles are not 3-common

Pages: 1 – 14

DOI: http://dx.doi.org/10.4310/JOC.2011.v2.n1.a1

#### Authors

#### Abstract

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.