孔祥艳. 路图P3(G)的色数(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2008, 111(3): 298-302.DOI:
路图P3(G)的色数(英文)
摘要
设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.
Abstract
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
χ(P3(G))≤β(G)
where β(G) is the vertex covering number of G. For a connected graph G of order at least 3
χ(P3(G))≤2 if and only if G is bipartite. Furthermore
χ(P3(G))=1 if and only if G is a star. For a K4-subdivision graph G
2≤χ(P3(G))≤3. For a series-parallel graph or an outerplanar graph G
χ(P3(G))≤3.
关键词
Keywords
references
Bondy J A, Murty U S R. Graph Theory With Application[M]. New York: Macmillan London and Elsevier,1976.
Duffin R J. Topology of series-parallel networks[J].Math Anal, 1965, (10):303-318.
Broersma H J, Hoede C. Path graphs[J]. Joural of Graph Theory,1989,13(2):427-444.
Rodrigues R M N D, Abreu N M M, Markenzon L.Maxregularity and Maximal outerplanar graphs[J]. Electronic Notes in Discrete Mathematics,1999(3):171-175.