On Seymour’s strengthening of Hadwiger’s conjecture for graphs with certain forbidden subgraphs

Let H be a set of graphs. A graph is called H -free if it does not contain a copy of a member of H as an induced subgraph. If H is a graph then G is called H -free if it is { H } -free. Plummer, Stiebitz, and Toft proved that, for every K 3 ¯ -free graph H on at most four vertices, every { K 3 ¯ , H } -free graph G has a collection of ⌈ | V ( G ) | / 2 ⌉ many pairwise adjacent vertices and edges (where a vertex v and an edge e are adjacent if v is disjoint from the set V ( e ) of endvertices of e and adjacent to some vertex of V ( e ) , and two edges e and f are adjacent if V ( e ) and V ( f ) are disjoint and some vertex of V ( e ) is adjacent to some vertex of V ( f ) ). Here we generalize this statement to K 3 ¯ -free graphs H on at most five vertices.