A universal partition result for infinite homogeneous Kn-free and related graphs
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
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
| Originalsprache | Englisch |
|---|---|
| Aufsatznummer | 112153 |
| Fachzeitschrift | Discrete Mathematics |
| Jahrgang | 344 |
| Ausgabenummer | 1 |
| Publikationsstatus | Veröffentlicht - Jan. 2021 |
| Peer-Review-Status | Ja |
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- Balanced partition, Henson graphs, Independent set, K-free, Monochromatic, Ramsey property