Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9516054 | Journal of Combinatorial Theory, Series B | 2005 | 16 Pages |
Abstract
Since Ï(G)·α(G)⩾n(G), Hadwiger's conjecture implies that any graph G has the complete graph Kân/αâ as a minor, where n=n(G) is the number of vertices of G and α=α(G) is the maximum number of independent vertices in G. Duchet and Meyniel [Ann. Discrete Math. 13 (1982) 71-74] proved that any G has Kân/(2α-1)â as a minor. For α(G)=2G has Kân/3â as a minor. Paul Seymour asked if it is possible to obtain a larger constant than 13 for this case. To our knowledge this has not yet been achieved. Our main goal here is to show that the constant 1/(2α-1) of Duchet and Meyniel can be improved to a larger constant, depending on α, for all α⩾3. Our method does not work for α=2 and we only present some observations on this case.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ken-ichi Kawarabayashi, Michael D. Plummer, Bjarne Toft,