Excluding pairs of graphs

For a graph G   and a set of graphs HH, we say that G   is HH-free if no induced subgraph of G   is isomorphic to a member of HH. Given an integer P>0P>0, a graph G  , and a set of graphs FF, we say that G admits an  (F,P)(F,P)-partition if the vertex set of G can be partitioned into P   subsets X1,…,XPX1,…,XP, so that for every i∈{1,…,P}i∈{1,…,P}, either |Xi|=1|Xi|=1, or the subgraph of G   induced by XiXi is {F}{F}-free for some F∈FF∈F.Our first result is the following. For every pair (H,J)(H,J) of graphs such that H   is the disjoint union of two graphs H1H1 and H2H2, and the complement JcJc of J   is the disjoint union of two graphs J1c and J2c, there exists an integer P>0P>0 such that every {H,J}{H,J}-free graph has an ({H1,H2,J1,J2},P)({H1,H2,J1,J2},P)-partition. A similar result holds for tournaments, and this yields a short proof of one of the results of [1].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,H2H1,H2, we say that G   is {H1,H2}{H1,H2}-split   if V(G)=X1∪X2V(G)=X1∪X2, where the subgraph of G   induced by XiXi is {Hi}{Hi}-free for i=1,2i=1,2. Our second result is that for every integer k>0k>0 and pair {H,J}{H,J} of cographs each of height k+1k+1, where neither of H,JcH,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}{H,J}-free graph is {H˜,J˜}-split.Our final result is a construction showing that if {H,J}{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}{H,J}-split, but G   does not admit an ({H,J},k)({H,J},k)-partition.