Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2308.16728 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915441814798336 |
|---|---|
| author | Byrne, John Tait, Michael Timmons, Craig |
| author_facet | Byrne, John Tait, Michael Timmons, Craig |
| contents | A graph is called an $(r,k)$-graph if its vertex set can be partitioned into $r$ parts, each having at most $k$ vertices and there is at least one edge between any two parts. Let $f(r,H)$ be the minimum $k$ for which there exists an $H$-free $(r,k)$-graph. In this paper we build on the work of Axenovich and Martin, obtaining improved bounds on this function when $H$ is a complete bipartite graph or an even cycle. Some of these bounds are best possible up to a constant factor and confirm a conjecture of Axenovich and Martin in several cases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_16728 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Forbidden subgraphs and complete partitions Byrne, John Tait, Michael Timmons, Craig Combinatorics A graph is called an $(r,k)$-graph if its vertex set can be partitioned into $r$ parts, each having at most $k$ vertices and there is at least one edge between any two parts. Let $f(r,H)$ be the minimum $k$ for which there exists an $H$-free $(r,k)$-graph. In this paper we build on the work of Axenovich and Martin, obtaining improved bounds on this function when $H$ is a complete bipartite graph or an even cycle. Some of these bounds are best possible up to a constant factor and confirm a conjecture of Axenovich and Martin in several cases. |
| title | Forbidden subgraphs and complete partitions |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2308.16728 |