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.
ASJC Scopus subject areas
- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics