图的全着色研究综述  

A survey on total coloring of graphs

作　　者：朱恩强 ZHU En-qiang(Institute of Computing Science and Technology,Guangzhou University,Guangzhou 510006,China)

机构地区：[1]广州大学计算科技研究院

出　　处：《广州大学学报（自然科学版）》2019年第4期9-27,共19页Journal of Guangzhou University:Natural Science Edition

基　　金：国家自然科学基金资助项目(61872101,61876047)

摘　　要：图的全着色是图的顶点着色和边着色的扩展,它要求对图的顶点和边同时进行着色,使得任意两个相邻元素(相邻点和相邻边)着不同颜色并且任意两个关联元素(边及其端点)也着不同颜色.图的全色数指的是该图所有全着色中所用的最少颜色数.关于该参数,Vizing(1964)和Behzed(1965)分别独立地提出猜想:任意图G的全色数不超过Δ(G)+2,其中Δ(G)表示图G的最大度.该猜想至今仍未解决,文章将对图的全着色研究进行全面的综述.The total coloring of a graph is the generalization of its vertex coloring and edge coloring,whose requirement is to assign colors to both its vertices and edges such that any adjacent elements(adjacent vertices and adjacent edges)and incident elements(vertices and edges)do not receive the same color.The total chromatic number of a graph is the minimum integer for which the graph admits a total coloring.In terms of this graph parameter,Vizing(1964)and Behzed(1965)independently proposed an identical conjecture:every graph has a total coloring using at mostΔ+2 colors,whereΔdenotes the maximum degree of the graph.This conjecture is still open.This paper will present a comprehensive survey on this topic.

关 键 词：全着色 全色数 全着色猜想 

分 类 号：O157.5[理学—数学]