The four-colour theorem states that every planar graph is -colourable. Infact this theorem can be extended to graphs with no -minor. It means that graphs with no -minor are -colourable. The Hadwiger’s conjecture is an extension of this theorem that states for every integer , every graph with no minor is -colourable. The Hadwiger’s conjecture for number is shown by . So far, this conjecture has been proved for , but is has not for although there have been several attempts which are near to a complete proof.
