Skip to main content

Excluding Pairs of Graphs

Author(s): Chudnovsky, Maria; Scott, Alex; Seymour, Paul D.

To refer to this page use:
Abstract: For a graph $G$ and a set of graphs $\mathcal{H}$, we say that $G$ is {\em $\mathcal{H}$-free} if no induced subgraph of $G$ is isomorphic to a member of $\mathcal{H}$. Given an integer $P>0$, a graph $G$, and a set of graphs $\mathcal{F}$, we say that $G$ {\em admits an $(\mathcal{F},P)$-partition} if the vertex set of $G$ can be partitioned into $P$ subsets $X_1,..., X_P$, so that for every $i \in \{1,..., P\}$, either $|X_i|=1$, or the subgraph of $G$ induced by $X_i$ is $\{F\}$-free for some $F \in \mathcal{F}$. Our first result is the following. For every pair $(H,J)$ of graphs such that $H$ is the disjoint union of two graphs $H_1$ and $H_2$, and the complement $J^c$ of $J$ is the disjoint union of two graphs $J_1^c$ and $J_2^c$, there exists an integer $P>0$ such that every $\{H,J\}$-free graph has an $(\{H_1,H_2,J_1,J_2\},P)$-partition. Using a similar idea we also give a short proof of one of the results of \cite{heroes}. Our final result is a construction showing that if $\{H,J\}$ are graphs each with at least one edge, then for every pair of integers $r,k$ there exists a graph $G$ such that every $r$-vertex induced subgraph of $G$ is $\{H,J\}$-split, but $G$ does not admit an $(\{H,J\},k)$-partition.
Publication Date: May-2014
Electronic Publication Date: 31-Jan-2014
Citation: M. Chudnovsky, A. Scott, P. Seymour, Excluding pairs of graphs, J. Combin. Theory Ser. B 106 (2014) 15–29.
DOI: 10.1016/j.jctb.2014.01.001
Pages: 15-29
Type of Material: Journal Article
Journal/Proceeding Title: Journal of combinatorial theory. Series B.
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.