Abstract
We develop lower bounds on the Hadwiger number h(G) of graphs G with high chromatic number. In particular, if G has n vertices and chromatic number k then h(G) ≥ (4k - n)/3.
Original language | English (US) |
---|---|
Pages (from-to) | 513-518 |
Number of pages | 6 |
Journal | Combinatorics Probability and Computing |
Volume | 20 |
Issue number | 4 |
DOIs | |
State | Published - Jul 2011 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics