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 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. Aharoni, Berger, Chudnovsky and Ziani 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 Kaiser and Rabinovich, 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.
@article{10_37236_5532,
author = {Alfr\'ed Gy\'arf\'as and Jeno Lehel},
title = {Red-blue clique partitions and \((1-1)\)-transversals},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {3},
doi = {10.37236/5532},
zbl = {1344.05106},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5532/}
}
TY - JOUR
AU - Alfréd Gyárfás
AU - Jeno Lehel
TI - Red-blue clique partitions and \((1-1)\)-transversals
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/5532/
DO - 10.37236/5532
ID - 10_37236_5532
ER -
