En teoria de grafs, la conjectura de Heawood o el teorema de Ringel-Youngs estableix una fita inferior per al nombre de colors que són necessaris per acolorir un graf en una superfície d'un gènere determinat. Va ser formulada el 1890 per John Percy Heawood i demostrada el 1968 per Gerhard Ringel i Ted Youngs. Un dels casos, l'ampolla de Klein no orientable, va resultar ser una excepció a la fórmula general. Es va necessitar un enfocament totalment diferent per al problema de trobar el nombre de colors necessaris per al pla, o de forma equivalent, l'esfera, resolt el 1976 com el teorema dels quatre colors per Wolfgang Haken i Kenneth Appel. La dificultat d'aquest problema canvia completament segons la forma de la superfície. En el cas de l'esfera, el més fàcil és trobar un mapa que necessiti quatre colors, però el gran repte va ser demostrar que quatre colors són suficients per a qualsevol mapa possible (fita superior). En canvi, per a superfícies amb gèneres més complexos passa al revés: Heawood va demostrar fàcilment quin era el límit màxim de colors en el seu article original, però la part realment difícil —que va requerir gairebé un segle de feina— va ser construir els mapes concrets que demostressin que tots aquests colors eren realment necessaris (fita inferior).
Vegeu també Teorema dels quatre colors Teorema dels cinc colors
Bibliografia
Heawood