To refer to this page use:

`http://arks.princeton.edu/ark:/88435/pr1c38z`

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.