Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture (Q2565692): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q175592 |
||
Property / author | |||
Property / author: Q788735 / rank | |||
Revision as of 06:14, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture |
scientific article |
Statements
Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture (English)
0 references
28 September 2005
0 references
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?
0 references
independence number
0 references
connected matching
0 references