Red-blue clique partitions and \((1-1)\)-transversals (Q311567): Difference between revisions

Summary: Motivated by the problem of \textit{T. Gallai} on \((1-1)\)-transversals of 2-intervals [Theory of Graphs, Proc. Colloq. Tihany, Hungary 1966, 115--118 (1968; Zbl 0159.54403)], it was proved by the authors [Combinat. Theory Appl., Colloquia Math. Soc. János Bolyai 4, 571--584 (1970; Zbl 0208.52202)] that if the edges of a complete graph \(K\) are colored with red and blue (both colors can appear on an edge) so that there is no monochromatic induced \(C_4\) and \(C_5\) then the vertices of \(K\) can be partitioned into a red and a blue clique. \textit{R. Aharoni} et al. [J. Comb. Theory, Ser. B 114, 170--186 (2015; Zbl 1315.05096)] recently strengthened this by showing that it is enough to assume that there is no induced monochromatic \(C_4\) and there is no induced \(C_5\) in one of the colors. Here this is strengthened further, it is enough to assume that there is no monochromatic induced \(C_4\) and there is no \(K_5\) on which both color classes induce a \(C_5\).{ }We also answer a question of \textit{T. Kaiser} and \textit{Y. Rabinovich} [Discrete Comput. Geom. 21, No. 2, 275--287 (1999; Zbl 0923.52002)], giving an example of six 2-convex sets in the plane such that any three intersect but there is no \((1-1)\)-transversal for them.