Compression and Erdős–Ko–Rado graphs Original Research Article

For a graph image and integer image we denote the collection of independent image-sets of image by image. If image then image is the collection of all independent image-sets containing image. A graph image, is said to be image-EKR, for image, iff no intersecting family image is larger than image. There are various graphs that are known to have his property: the empty graph of order image (this is the celebrated Erdős–Ko–Rado theorem), any disjoint union of at least image copies of image for image, and any cycle. In this paper we show how these results can be extended to other classes of graphs via a compression proof technique. In particular we extend a theorem of Berge (Hypergraph Seminar, Columbus, Ohio 1972, Springer, New York, 1974, pp. 13–20.), showing that any disjoint union of at least image complete graphs, each of order at least two, is image-EKR. We also show that paths are image-EKR for all image.