Red-blue clique partitions and (1-1)-transversals

Andras Gyarfas, Jeno Lehel

Motivated by the problem of Gallai on $(1-1)$-transversals of $2$-intervals, it was proved by the authors in 1969 that if the edges of a complete graph $K$ are colored with red and…