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.
@article{10_37236_12354,
author = {John Byrne and Michael Tait and Craig Timmons},
title = {Forbidden subgraphs and complete partitions},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {4},
doi = {10.37236/12354},
zbl = {8120088},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12354/}
}
TY - JOUR
AU - John Byrne
AU - Michael Tait
AU - Craig Timmons
TI - Forbidden subgraphs and complete partitions
JO - The electronic journal of combinatorics
PY - 2025
VL - 32
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/12354/
DO - 10.37236/12354
ID - 10_37236_12354
ER -
%0 Journal Article
%A John Byrne
%A Michael Tait
%A Craig Timmons
%T Forbidden subgraphs and complete partitions
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/12354/
%R 10.37236/12354
%F 10_37236_12354
John Byrne; Michael Tait; Craig Timmons. Forbidden subgraphs and complete partitions. The electronic journal of combinatorics, Tome 32 (2025) no. 4. doi: 10.37236/12354
