Clique Minors in Graphs and Their Complements

✍ Scribed by Bruce Reed; Robin Thomas

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 107 KB
• Volume: 78
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1999.1930

✦ Synopsis

A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. Let t 1 be an integer, and let G be a graph on n vertices with no minor isomorphic to K t+1 . Kostochka conjectures that there exists a constant c=c(t) independent of G such that the complement of G has a minor isomorphic to K s , where s=W 1 2 (1+1Ât) n&cX . We prove that Kostochka's conjecture is equivalent to the conjecture of Duchet and Meyniel that every graph with no minor isomorphic to K t+1 has an independent set of size at least nÂt. We deduce that Kostochka's conjecture holds for all integers t 5, and that a weaker form with s replaced by s$=W 1 2 (1+1Â(2t)) n&cX holds for all integers t 1.

2000 Academic Press

All graphs in this note are simple (that is, they have no loops or parallel edges) and finite. By considering the largest color class Hadwiger's conjecture implies a conjecture of Duchet and Meyniel [1], the following.