Clique Covers of Complete Graphs and Piercing Multitrack Intervals

Barát, János and Gyárfás, András and Sárközy, Gábor (2025) Clique Covers of Complete Graphs and Piercing Multitrack Intervals. ELECTRONIC JOURNAL OF COMBINATORICS, 32 (3). ISSN 1097-1440

Preview

Text 13267-PDFfile-56565-2-10-20250910.pdf Download (315kB) | Preview

Abstract

Assume that are disjoint parallel lines in the plane. A -interval (or -track interval) is a set that can be written as the union of closed intervals, each on a different line. It is known that pairwise intersecting -intervals can be pierced by two points, one from each line. However, it is not true that every set of pairwise intersecting -intervals can be pierced by three points, one from each line. For , Kaiser and Rabinovich asked whether -wise intersecting -intervals can be pierced by points, one from each line. Our main result provides a positive answer in an asymptotic sense: in any set of -wise intersecting -intervals, at least can be pierced by 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 -free graphs. For instance, we show that if the edges of a complete graph are colored with red or blue so that both color classes are induced -free, then at least 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.

Actions (login required)

Edit Item