图的全着色是图的顶点着色和边着色的扩展,它要求对图的顶点和边同时进行着色,使得任意两个相邻元素(相邻点和相邻边)着不同颜色并且任意两个关联元素(边及其端点)也着不同颜色.图的全色数指的是该图所有全着色中所用的最少颜色数.关于该参数,Vizing(1964)和Behzed(1965)分别独立地提出猜想:任意图G的全色数不超过Δ(G)+2,其中Δ(G)表示图G的最大度.该猜想至今仍未解决,文章将对图的全着色研究进行全面的综述.
科研之友
微信
新浪微博
Facebook
分享链接
