On Connected Components with Many Edges

Abstract: We prove that if

H

is a subgraph of a complete multipartite graph

G

, then

H

contains a connected component

H^{'}

satisfying

| E (H^{'}) | | E (G) | g e q | E (H) |^{2}

. We use this to prove that every three-coloring of the edges of a complete graph contains a monochromatic connected subgraph with at least

1 / 6

of the edges. We further show that such a coloring has a monochromatic circuit with a fraction

1 / 6 - o (1)

of the edges. This verifies a conjecture of Conlon and Tyomkyn. Moreover, for general

k

, we show that every

k

-coloring of the edges of

K_{n}

contains a monochromatic connected subgraph with at least

edges.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: On Connected Components with Many Edges