Name
Abstract | ||
|---|---|---|
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 |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1017/S0963548305006759 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
chromatic number,connected matchings,maximum number,pairwise nonadjacent vertex | Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
14 | 3 | 0963-5483 |
Citations | PageRank | References |
4 | 0.68 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zoltán Füredi | 1 | 1237 | 233.60 |
| András Gyárfás | 2 | 582 | 102.26 |
| Gábor Simonyi | 3 | 249 | 29.78 |