Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

("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 .

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.