版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构: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.