中国科学A辑
中國科學A輯
중국과학A집
SCIENCE IN CHINA (SERIES A)
2006年
12期
1321-1326
,共6页
全色数%平面图%F5子图
全色數%平麵圖%F5子圖
전색수%평면도%F5자도
用△(G),χve(G)分别表示图G的顶点最大度和全色数.Vizing猜想:对任何简单图G,△(G)+1≤χve(G)≤△(G)+2.即使对于平面图,这一猜想仍未获得完整的证明,唯一待完成的困难情形是△(G)=6.本文证明:若△(G)=6的平面图G不含有4圈,则χve(G)≤8.这一结果和以前在该问题上的已知结果表明:对于不含有4圈的平面图,Vizing猜想是正确的.
用△(G),χve(G)分彆錶示圖G的頂點最大度和全色數.Vizing猜想:對任何簡單圖G,△(G)+1≤χve(G)≤△(G)+2.即使對于平麵圖,這一猜想仍未穫得完整的證明,唯一待完成的睏難情形是△(G)=6.本文證明:若△(G)=6的平麵圖G不含有4圈,則χve(G)≤8.這一結果和以前在該問題上的已知結果錶明:對于不含有4圈的平麵圖,Vizing猜想是正確的.
용△(G),χve(G)분별표시도G적정점최대도화전색수.Vizing시상:대임하간단도G,△(G)+1≤χve(G)≤△(G)+2.즉사대우평면도,저일시상잉미획득완정적증명,유일대완성적곤난정형시△(G)=6.본문증명:약△(G)=6적평면도G불함유4권,칙χve(G)≤8.저일결과화이전재해문제상적이지결과표명:대우불함유4권적평면도,Vizing시상시정학적.