Title :
The Research on Two Important Counter-Examples of Four-Color Problem
Author :
Wang Jinbiao ; Qin Shu
Author_Institution :
Comput. Sci. & Technol. Coll., Civil Aviation Univ. of China, Tianjin, China
Abstract :
This paper proves that counterexample of Heawood is four-colorable by using Tait´s methods and that counterexample of Tutte is also four-colorable by using Kempe´s chains. Authors discover formation mechanism of two-level Hamilton cycle in a 3-regular plane graph. It provides a new way for the non-computer proof of four-color problem.
Keywords :
geometry; graph theory; Heawood; Kempe chains; Tait methods; four-color problem; plane graph; two-level Hamilton cycle; Computer science; Computer security; Geometry; Informatics; Information security; Information technology; Paper technology; Research and development; Tail; Heawood-counterexample; Kempe´s chains; Tait conjecture; Tutte-counterexample; two-level Hamilton cycle;
Conference_Titel :
Intelligent Information Technology and Security Informatics (IITSI), 2010 Third International Symposium on
Conference_Location :
Jinggangshan
Print_ISBN :
978-1-4244-6730-3
Electronic_ISBN :
978-1-4244-6743-3
DOI :
10.1109/IITSI.2010.158
