Carnegie Mellon University
Browse
file.pdf (205.9 kB)

Graphs containing triangles are not 3-common

Download (205.9 kB)
journal contribution
posted on 2011-01-01, 00:00 authored by James CummingsJames Cummings, Michael Young

A finite graph G is {\em k-common} if the minimum (over all k-colourings of the edges of Kn) 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 Kn. Jagger, \u{S}\u{t}oví\u{c}ek and Thomason showed that graphs which contain K4 are not 2-common. We prove that graphs which contain K3 are not 3-common.

History

Publisher Statement

© by International Press of Boston

Date

2011-01-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC