图的路色数

Path Chromatic Number of Graphs

设G=(V,E)是一个简单图.称V 的一个划分{V_1,V_2,…,V_φ}是一个路着色,如果对任意的i∈{1,2,…,k},〈V_i〉的每个分支都是路.G 的路着色中所需的最少颜色数叫G 的路色数.本文给出了路色数的一个下界;并讨论了两个图的笛卡儿积的路色数,最后,还推广了文[1]的一个定理的结论.

Let G=(V,E)be a simple graph.A partition{V_1,V_2,...V_k}of V is apath-coloring if,for any i∈{1,2,...,k},each component of〈V_i〉is a path.The path chromatic number of G,denoted by X(G,P),is the minimumnumber of colors needed in a path-coloring of G.In this paper,we obtainlower bound of X(G,P),and discuss X(G_1×G_2,P),where G_1×G_2 is theCartesian product of G_1 and G_2.