路图P_3(G)的色数(英文)  

On the Chromatic Number of Path Graph P_3(G)

作　　者：孔祥艳[1] 

机构地区：[1]新疆大学数学与系统科学学院,新疆乌鲁木齐830046

出　　处：《新疆大学学报（自然科学版）》2008年第3期298-302,共5页Journal of Xinjiang University(Natural Science Edition)

摘　　要：设G是一个图,G的路图P3(G)的顶点集是G中所有三个顶点的路P3,当G中的两个P3路形成P4路或C3圈时,在P3(G)中它们所代表的两个顶点相邻.在这篇文章中,我们得到对于一个无三角形的图G,χ(P3(G))≤β(G),其中β(G)表G的点覆盖数.对于顶点数至少为3的连通图G,χ(P3(G))≤2当且仅当G是二部图,并且χ(P3(G))=1当且仅当G是星图.对于K4的剖分图G,2≤χ(P3(G))≤3.对于系列平行图和外可平面图G,χ(P3(G))≤3.Let G be a graph. The path graph P3 （G） of G is obtained by representing the paths P3 in G by vertices and joining two vertices whenever the corresponding paths P3 in G form a path P4 or a cycle C3.In this paper, we show that for a triangle-free graph G,X（P3 （G））≤β（G） , where β（G） is the vertex covering number of G. For a connected graph G of order at least 3, X（P3 （G）） ≤2 if and only if G is bipartite. Furthermore,X（P3 （G）） = 1 if and only ifG is a star. For a K4-subdivision graph G,2≤X（P3（G））≤3. For a series-parallel graph or an outerplanar graph G , X（P3 （G））≤3.

关 键 词：色数 路图 线图 无三角形的图 K4的剖分图 系列平行图 外可平面图 

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