关于图的路色数的一些结果  

SOME RESULTS ABOUT PATH CHROMATIC NUMBER OF GRAPHS

作　　者：原晋江 林诒勋 

机构地区：[1]郑州大学数学系

出　　处：《郑州大学学报（自然科学版）》1992年第4期1-8,共8页Journal of Zhengzhou University (Natural Science)

摘　　要：本文研究图的路色数.首先得到图的路色数的一些基本性质;其次给出图G满足χ(G;P2)≤2的一个充分必要条件,该条件可以有效地应用于极大平面图和2-连通极大外平面图;最后证明了图的k-路色数问题的NP-完全性(k≥3).This paper deals with path chromatic number of graphs. Our main results are as follows; Some fundamental properties of path chromatic number;A necessary and sufficient condition for a graph G with X(G;P_2)≤2, which can be used in maximal plane graphs and 2-connected maximal outerplane graphs efficiently;The NP-completeness of the problem to determine whether X(G; P_k)≤3 (k≥3) or not for a graph G.

关 键 词：图 路色数 NP-完全 着色 

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