Subcontraction‐equivalence and Hadwiger's conjecture

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 K m +1 as a subcontraction must contain an independent set consisting of at least 1/2( m − 1) of its vertices.