Finding Large Monochromatic Diameter Two Subgraphs

Abstract

Given a coloring of the edges of the complete graph on n vertices in k colors, by considering the neighbors of an arbitrary vertex it follows that there is a monochromatic diameter two subgraph on at least 1+(n-1)/k vertices. We show that for $k\ge 3$ this is asymptotically best possible, and that for k=2 there is always a monochromatic diameter two subgraph on at least $\lceil \frac{3}{4}n\rceil$ vertices, which again, is best possible.

20 pages

Cited by in corpus (1)

• Large monochromatic triple stars in edge colourings