高度不正则图的全着色
Total Colouring of Highly Irregular Graph
-
摘要: 图G的正常k全着色是指用k种颜色对G的点和边着色,使相邻或相关联的元素(点或边)着不同色。其中最小的k称为G的全色数,记为χT(G)。设G是一个简单图,υ是G的任意一个顶点,若与υ相邻的顶点的度互不相同,则称G为高度不正则图。对高度不正则图G,文中证明了χT(G)=Δ(G)+1,同时也给出了着色的算法,其中Δ(G)为G的最大度数且Δ(G)≥ 2。Abstract: A proper k -total colouring of a graph G is a colouring to its vertices and edges using k colours such that no two adjacent or incident elements (vertices or edges) of G may be assigned the same colour.The k is called total chromatic number of graph G if k is minimal.The symbol χT(G) is used to denoted the chromatic number.We call a simple graph G a highly irregular graph if the degree of u' is not equal to the degree of u″ for any u',u″∈N(v) and for any vertex v of G,where N(v) is the neighborhood of v.Let G be a highly irregular graph and Δ(G) is its maximum degree.We show that if Δ(G) ≥ 2,then χT(G)=Δ(G)+1.A total colouring algorithm of G is also obtained.