摘要
本文研究图的路色数.首先得到图的路色数的一些基本性质;其次给出图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.
出处
《郑州大学学报（自然科学版）》
CAS
1992年第4期1-8,共8页
Journal of Zhengzhou University (Natural Science)
关键词
图
路色数
NP-完全
着色
graph
path chromatic number
NP-complete
