路图P<sub>3</sub>(G)的色数(英文)

孔祥艳

您当前的位置：

首页 >

文章列表页 >

路图P₃(G)的色数(英文)

数理科学 | 更新时间：2026-01-21

- 路图P₃(G)的色数(英文)
- 路图P₃(G)的色数(英文)
- 新疆大学学报（自然科学版中英文） 2008年111卷第3期页码：298-302
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
- DOI：
  中图分类号： O157.5
- 纸质出版：2008
- 稿件说明：
移动端阅览
[1]孔祥艳.路图P_3(G)的色数(英文)[J].新疆大学学报(自然科学版),2008,No.111(03):298-302.

孔祥艳. 路图P₃(G)的色数(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2008, 111(3): 298-302.
[1]孔祥艳.路图P_3(G)的色数(英文)[J].新疆大学学报(自然科学版),2008,No.111(03):298-302. DOI：

孔祥艳. 路图P₃(G)的色数(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2008, 111(3): 298-302. DOI：

摘要

设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.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

P₄-free图的控制团及应用(英文)

立方体的线图的限制性连通度(英文)

线图的邻域连通度(英文)

图的色数的一个上界

线团图的一些性质

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

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

DOI：

摘要

Abstract

关键词

Keywords

references

路图P₃(G)的色数(英文)

路图P₃(G)的色数(英文)