Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture (Q2565692): Difference between revisions

The well-known Hadwiger's conjecture states that every graph \(G\) has the complete graph \(K_{\chi(G)}\) as a minor where \(\chi(G)\) denotes the chromatic number of \(G\). \textit{D. R. Woodall} [J. Graph Theory 11, 197--204 (1987; Zbl 0672.05027)] conjectured that every graph \(G\) with \(n\geq 1\) vertices has \(K_{\lceil \frac{1}{\alpha(G)}n\rceil}\) as a minor where \(\alpha(G)\) denotes the independence number of \(G\). As \(\chi(G)\alpha(G)\geq n\), Hadwiger's conjecture implies Woodall's conjecture. In case \(\alpha(G)=2\), however, the two conjectures are equivalent [\textit{M. D. Plummer, M. Stiebitz} and \textit{B. Toft}, Discuss. Math., Graph Theory 23, 333-363 (2003; Zbl 1053.05052)]. In this context, a theorem of \textit{P. Duchet} and \textit{H. Meyniel} [Ann. Discrete Math. 13, 71--73 (1982; Zbl 0522.05060)] states that every graph \(G\) has a \(K_{\lceil \frac{1}{2\alpha(G)-1}n\rceil}\) as a minor. In this paper, the authors improve the theorem above as follows: (1) Every graph \(G\) with \(n\) vertices, clique number \(w(G)\) and independence number \(\alpha(G)\geq 2\) has \(K_{\lceil \frac{1}{2\alpha(G)-1}(n+\omega(G))\rceil}\) as a minor, (2) Every graph \(G\) with \(n\) vertices and independence number \(\alpha(G)\geq 3\) has \(K_{\lceil \frac{1}{(4\alpha(G)-3)(2\alpha(G)-1)}(n(4\alpha(G)-2))\rceil}\) as a minor, and (3) Let \(G\) be a graph with \(n\) vertices and \(\alpha(G)=2\). If \(G\) is \((n-4)\)-connected, then \(G\) has \(K_{\lceil \frac{1}{2}n\rceil}\) as a minor. For general graphs \(G\) with \(\alpha(G)=2\), a problem due to Paul Seymour still remains open. It reads: Is it possible to obtain a larger constant than \(\frac{1}{3}\) in the theorem of Duchet and Meyniel?