Matchings and Hadwiger's conjecture (Q1349093): Difference between revisions

Hadwiger's conjecture says that every graph of chromatic number \(k\) contains a \(K_k\)-minor. Although verified for \(k\leq 6\) so far, in general it still remains open. Suppose that graph \(G\) on \(n\) vertices is the only counterexample to the conjecture among its induced subgraphs and investigate the properties of its complement \(H\). The main results of this article are that then \(H\) contains a matching of size \(\lfloor n/2\rfloor\), is a subdivision of a 3-connected graph and has tree width at least 4. It is also observed that the same results are true for Colin de Verdière's conjecture \(\chi(G)\leq\mu(G)+1\) introduced in [J. Comb. Theory, Ser. B 50, 11-21 (1990; Zbl 0742.05061)].