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

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

  • Andres Aranda - , Chair of Algebra and Discrete Structures (Author)
  • Claude Laflamme - , University of Calgary (Author)
  • Daniel T. Soukup - , Mostly AI (Author)
  • Robert Woodrow - , University of Calgary (Author)

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

Original languageEnglish
Article number112153
JournalDiscrete Mathematics
Volume344
Issue number1
Publication statusPublished - Jan 2021
Peer-reviewedYes

Keywords

Keywords

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