Conjectura de Heawood

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. En l'esfera la fita inferior és fàcil, mentre que gèneres més grans la fita superior és fàcil i va ser demostrada en el breu article original de Heawood que contenia la conjectura.

Vegeu també

• Teorema dels quatre colors
• Teorema dels cinc colors

Bibliografia

• Franklin, P. «A six color problem». Journal of Mathematical Physics, 13, 1934, pàg. 363–379.
• Heawood, P. J. «Map colour theorem». Quarterly Journal of Mathematics, 24, 1890, pàg. 332–338.
• Ringel, G.; Youngs, J. W. T. «Solution of the Heawood map-coloring problem». Proceedings of the National Academy of Sciences of the United States of America, 60, 2, 1968, pàg. 438–445. DOI: 10.1073/pnas.60.2.438. PMC: 225066. PMID: 16591648.