Proof of Toft's conjecture:: Every graph containing no fully odd K₄ is 3-colorable

作     者：Zang, W 

作者机构：Univ Hong Kong Dept Math Hong Kong Hong Kong 

出 版 物：《JOURNAL OF COMBINATORIAL OPTIMIZATION》 (组合优化杂志)

年 卷 期：1998年第2卷第2期

页      面：117-188页

核心收录：

学科分类：12[管理学] 120202[管理学-企业管理（含：财务管理、市场营销、人力资源管理）] 0202[经济学-应用经济学] 02[经济学] 1202[管理学-工商管理] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：RGC, (338/024/0009) Rutgers University Air Force Office of Scientific Research, AFOSR, (F49620-93-1-0041) 

主　　题：graph coloring chromatic number minor subdivision polynomial time algorithm 

摘      要：A fully odd K-4 is a subdivision of K-4 such that each of the six edges of the K-4 is subdivided into a path of odd length. In 1974, Toft conjectured that every graph containing no fully odd K-4 can be vertex-colored with three colors. The purpose of this paper is to prove Toft s conjecture.