Hostname: page-component-74656f9884-kv2lp Total loading time: 0 Render date: 2026-11-05T23:19:57.402Z Has data issue: false hasContentIssue false

Connected matchings and Hadwiger's conjecture

Published online by Cambridge University Press:  11 April 2005

ZOLTÁN FÜREDI
Affiliation:
Alfréd Rényi Institute, Hungarian Academy of Sciences, Budapest 1364, P. O. Box 127, and Dept. of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL61801, USA (e-mail: furedi@renyi.huResearch partially supported by Hungarian National Science Foundation Grants OTKA T032452 and T037846 and by NSF grant DMS 0140692.)
ANDRÁS GYÁRFÁS
Affiliation:
Computer and Automation Research Institute of the Hungarian Academy of Sciences, Budapest, P. O. Box 63, Hungary-1518 (e-mail: gyarfas@sztaki.hu)
GÁBOR SIMONYI
Affiliation:
Alfréd Rényi Institute, Hungarian Academy of Sciences, Budapest 1364, P. O. Box 127 (e-mail: simonyi@renyi.huResearch partially supported by the Hungarian Foundation for Scientific Research Grant (OTKA) Nos. T037846 and T046376.)
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Hadwiger's well known conjecture (see the survey of Toft [9]) states that any graph $G$ has a $K_{\chi(G)}$ minor, where $\chi(G)$ is the chromatic number of $G$. Let $\alpha(G)$ denote the independence (or stability) number of $G$, namely the maximum number of pairwise nonadjacent vertices in $G$. It was observed in [1], [4], [10] that via the inequality $\chi(G)\ge {|V(G)|\over \alpha(G)}$, Hadwiger's conjecture implies

Conjecture 1.1. Any graph G on n vertices contains a $K_{\lceil {n\over \alpha(G)}\rceil}$ as a minor.

Information

Type
PROBLEM SECTION
Copyright
© 2005 Cambridge University Press