0
$\begingroup$

Please prove the following theorem from Gallai :

Theorem .In every coloring of a complete graph with three colors that avoiding rainbow triangle , at least one of the color classes must be disconnected.

1 Answers 1

2

("Rainbow triangle" means a triangle whose edges are colored with three different colors.)

This result goes back to a 1967 paper of Gallai. It is proved, as Lemma A, in the following paper: "Edge colorings of complete graphs without tricolored triangles", András Gyárfás, Gábor Simony, Journal of Graph Theory, 46, #3, pages 211–216, July 2004, doi: 10.1002/jgt.20001 .