La conjectura de Hadwiger és una de les conjectures més importants i conegudes de la teoria de grafs, proposada pel matemàtic suís Hugo Hadwiger l'any 1943. Estableix una relació profunda entre el nombre cromàtic d'un graf i l'existència de menors complets dins d'aquests.
La conjectura és considerada un dels problemes oberts més rellevants de la teoria de grafs, ja que generalitza diversos resultats fonamentals, com ara el teorema dels quatre colors.
Enunciat Per a qualsevol enter t més gran o igual que 1, qualsevol graf amb un nombre cromàtic χ(G) o més colors ha de contenir un menor (minor) del graf complet Kt
El nombre cromàtic χ(G) és el nombre mínim de colors necessaris per a pintar els vèrtexs d'un graf de manera que no hi hagi dos vèrtexs adjacents amb el mateix color. Un graf H és un menor d'un graf G si H es pot obtenir de G mitjançant una seqüència d'eliminacions de vèrtexs, eliminacions d'arestes i contraccions d'arestes. Una contracció d'aresta consisteix a fusionar els dos vèrtexs terminals d'una aresta en un únic vèrtex. El graf complet Kt és un graf on tots els t vèrtexs estan connectats entre si.
Categoria:Teoria de grafs Categoria:Conjectures