This is a survey of Hadwiger’s conjecture from 1943, that for all t ≥ 0, every graph either can be t-coloured, or has a subgraph that can be contracted to the complete graph on t + 1 vertices. This is a tremendous strengthening of the fourcolour theorem, and is probably the most famous open problem in graph theory.
All Science Journal Classification (ASJC) codes
- Economics, Econometrics and Finance(all)
- Business, Management and Accounting(all)