A universal partition result for infinite homogeneous Kn-free and related graphs

Abstract We study new partition properties of infinite K n -free graphs. First, we investigate the number bpi ( G , m ) introduced by A. Aranda et al. (denoted there by r ( G , m ) ) : the minimal r so that for any partition of G into r classes of equal size, there exists an independent set which meets at least m classes in size | G | . In the case of Henson’s countable universal K n -free graph H n , we express bpi ( H n m ) by well-known Ramsey-numbers for finite digraphs. In particular we answer a conjecture of Thomasse (2000) by showing that indeed bpi ( H n , 2 ) = 2 for all n ⩾ 3 . Furthermore, we bound and in some cases determine bpi ( G , m ) for certain geometric graphs, including shift graphs, unit distance graphs and orthogonality graphs. Second, we prove a new universal partition property for H n . Given a finite bipartite graph G on classes A , B , we show that for any balanced 2-colouring of H n there is an induced copy of G in H n so that the images of A and B are monochromatic of distinct colours. We end our paper with further open problems.