应用数学学报
應用數學學報
응용수학학보
ACTA MATHEMATICAE APPLICATAE SINICA
2013年
6期
988-999
,共12页
平面图%全染色%最大度%扇
平麵圖%全染色%最大度%扇
평면도%전염색%최대도%선
Plane graphs%total coloring%maximum degree%fan
设G=(V,E)是一个以V为顶点集,E为边集的图.图G的一个k-全染色是一个映射φ:V∪E→{1,2,…,k｝使得φ(x)≠φ(y)对所有相邻或相关联的元素x和y都成立.若G有一个k-全染色,则说G是k-全可染的.令△为G的最大度.显然,对G进行全染色,至少需要△+1个颜色.Behzad和Vizing相互独立地猜想每个(简单)图都是(△+2)-全可染的.已知最大度△≥9的平面图是(△+1)-全可染的.通过研究极小反例的新的可约性质,本文运用权转移方法证明了最大度为8且不含4-扇的平面图是9-全可染的,这里的4-扇是指交于一点的4个相继的3-面.这一结果改进了若干同类型的相关结果.
設G=(V,E)是一箇以V為頂點集,E為邊集的圖.圖G的一箇k-全染色是一箇映射φ:V∪E→{1,2,…,k｝使得φ(x)≠φ(y)對所有相鄰或相關聯的元素x和y都成立.若G有一箇k-全染色,則說G是k-全可染的.令△為G的最大度.顯然,對G進行全染色,至少需要△+1箇顏色.Behzad和Vizing相互獨立地猜想每箇(簡單)圖都是(△+2)-全可染的.已知最大度△≥9的平麵圖是(△+1)-全可染的.通過研究極小反例的新的可約性質,本文運用權轉移方法證明瞭最大度為8且不含4-扇的平麵圖是9-全可染的,這裏的4-扇是指交于一點的4箇相繼的3-麵.這一結果改進瞭若榦同類型的相關結果.
설G=(V,E)시일개이V위정점집,E위변집적도.도G적일개k-전염색시일개영사φ:V∪E→{1,2,…,k｝사득φ(x)≠φ(y)대소유상린혹상관련적원소x화y도성립.약G유일개k-전염색,칙설G시k-전가염적.령△위G적최대도.현연,대G진행전염색,지소수요△+1개안색.Behzad화Vizing상호독입지시상매개(간단)도도시(△+2)-전가염적.이지최대도△≥9적평면도시(△+1)-전가염적.통과연구겁소반례적신적가약성질,본문운용권전이방법증명료최대도위8차불함4-선적평면도시9-전가염적,저리적4-선시지교우일점적4개상계적3-면.저일결과개진료약간동류형적상관결과.
