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

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

Abstract

We study new partition properties of infinite Kn-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 Kn-free graph Hn, we express bpi(Hnm) by well-known Ramsey-numbers for finite digraphs. In particular we answer a conjecture of Thomassé (2000) by showing that indeed bpi(Hn,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 Hn. Given a finite bipartite graph G on classes A,B, we show that for any balanced 2-colouring of Hn there is an induced copy of G in Hn so that the images of A and B are monochromatic of distinct colours. We end our paper with further open problems.

Details

OriginalspracheEnglisch
Aufsatznummer112153
FachzeitschriftDiscrete Mathematics
Jahrgang344
Ausgabenummer1
PublikationsstatusVeröffentlicht - Jan. 2021
Peer-Review-StatusJa

Schlagworte

Schlagwörter

  • Balanced partition, Henson graphs, Independent set, K-free, Monochromatic, Ramsey property