Clique Covers of Complete Graphs and Piercing Multitrack Intervals

Assume that R₁,R₂,,Rₜ are disjoint parallel lines in the plane. A t-interval (or t-track interval) is a set that can be written as the union of t closed intervals, each on a different line. It is known that pairwise intersecting $2$-intervals can be pierced by two points, one from each line. However, it is not true that every set of pairwise intersecting $3$-intervals can be pierced by three points, one from each line. For k≥ 3, Kaiser and Rabinovich asked whether k-wise intersecting t-intervals can be pierced by t points, one from each line. Our main result provides a positive answer in an asymptotic sense: in any set S₁,,Sₙ of k-wise intersecting t-intervals, at least k-1/k+1n can be pierced by t points, one from each line. We prove this in a more general form, replacing intervals by subtrees of a tree. This leads to questions and results on covering vertices of edge-colored complete graphs by vertices of monochromatic cliques having distinct colors, where the colorings are chordal, or more generally induced C₄-free graphs. For instance, we show that if the edges of a complete graph Kₙ are colored with red or blue so that both color classes are induced C₄-free, then at least 4n 5 vertices can be covered by a red and a blue clique, and this is best possible. We conclude by pointing to new Ramsey-type problems emerging from these restricted colorings.