# Excluding pairs of graphs

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

## Abstract

For a graph G and a set of graphs H, we say that G is H-free if no induced subgraph of G is isomorphic to a member of H. Given an integer P>0, a graph G, and a set of graphs F, we say that G admits an (F,P)-partition if the vertex set of G can be partitioned into P subsets X1, . . XP, so that for every i∈{1, . . ., P}, either |Xi|=1, or the subgraph of G induced by Xi is {F}-free for some F∈F.Our first result is the following. For every pair (H, J) of graphs such that H is the disjoint union of two graphs H1 and H2, and the complement Jc of J is the disjoint union of two graphs J1c and J2c, there exists an integer P>0 such that every {H, J}-free graph has an ({H1, H2, J1, J2}, P)-partition. A similar result holds for tournaments, and this yields a short proof of one of the results of .A cograph is a graph obtained from single vertices by repeatedly taking disjoint unions and disjoint unions in the complement. For every cograph there is a parameter measuring its complexity, called its height. Given a graph G and a pair of graphs H1, H2, we say that G is {H1, H2}-split if V(G)=X1∪X2, where the subgraph of G induced by Xi is {Hi}-free for i=1, 2. Our second result is that for every integer k>0 and pair {H, J} of cographs each of height k+1, where neither of H, Jc is connected, there exists a pair of cographs (H~,J~), each of height k, where neither of H~c,J~ is connected, such that every {H, J}-free graph is {H~,J~}-split.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.

Original language English (US) 15-29 15 Journal of Combinatorial Theory. Series B 106 1 https://doi.org/10.1016/j.jctb.2014.01.001 Published - 2014

## All Science Journal Classification (ASJC) codes

• Theoretical Computer Science
• Discrete Mathematics and Combinatorics
• Computational Theory and Mathematics

## Keywords

• Cograph
• Induced subgraphs
• Ramsey theorem

## Fingerprint

Dive into the research topics of 'Excluding pairs of graphs'. Together they form a unique fingerprint.