Subcontraction‐equivalence and Hadwiger's conjecture
Douglas R. Woodall · Journal of Graph Theory · 1987
Abstract The concept of subcontraction‐equivalence is defined, and 14 graph‐theoretic properties are exhibited that are all subcontraction‐equivalent if Hadwiger's conjecture is true. Some subsets of these properties are proved to be subcontraction‐equivalent anyway. Hadwiger's conjecture is expressed as the union of three independent and strictly weaker subconjectures. As a first step toward one of these subconjectures, it is proved that a graph that does not have Km+1 as a subcontraction must contain an independent set consisting of at least 1/2(m − 1) of its vertices.