整数距离图G(Dm, k, 2)的点荫度

数学物理学报 ›› 2010, Vol. 30 ›› Issue (4): 968-983.

整数距离图G(D_{m, k,}₂)的点荫度

左连翠¹,崔玉泉²,刘家壮²

1.天津师范大学数学科学学院天津 300387|2.山东大学数学与系统科学院济南 250100

收稿日期:2007-04-18 修回日期:2009-09-18 出版日期:2010-07-25 发布日期:2010-07-25
基金资助:
天津师范大学引进人才基金(5RL066)资助

The Vertex Arboricity of Integer Distance Graphs G(D_{m, k}_{, 2})

ZUO Lian-Cui¹, CUI Yu-Quan², LIU Jia-Zhuang²

1.College of Mathematics Science, Tianjin Normal University, Tianjin 300387;
2.School of Mathematics |and System Science, Shandong University, Jinan |250100

Received:2007-04-18 Revised:2009-09-18 Online:2010-07-25 Published:2010-07-25
Supported by:
天津师范大学引进人才基金(5RL066)资助

摘要/Abstract

摘要：

图G 的点荫度va(G)是顶点集合V(G)能划分成的这样一些子集的最少数目, 其中任一子集的点导出子图都是森林. 整数距离图G(D)以全体整数作为顶点集, 顶点u, v相邻当且仅当 |u - v|∈D, 其中D是一个正整数集. 对于m>2k≥2, 令D_{m, k}_{, 2}=[1, m]\k, 2k\}. 该文得出了整数距离图G(D_{m, k}_{, 2})的点荫度的几个上、下界; 进而, 对于m≥4, 有va(G(D_m_{, 1, 2}))=[m+4/5]; 对于m=10q+j, j=0, 1, 2, 3, 5, 6, 有va(G(D_m_{, 2, 2}))=lm+1/5l+1.

关键词: 整数距离图, 点荫度, 树着色

Abstract:

The vertex arboricity va(G) of a graph G is the minimum number of subsets into which the vertex set V(G) can be partitioned so that each subset induces a subgraph whose connected components are trees. An integer distance graph is a graph G(D) with the set of all integers as vertex set and two vertices u, v\in Z are adjacent if and only if |u-v in D where the distance set D is a subset of the positive integers set. Let _{Dm, k, 2}=[1,m]\k, 2k} for m>2k≥2. In this paper, some upper and lower bounds of the vertex arboricity of the integer distance graph G(D_{m, k,}₂) are obtained. Moreover, va(G(D_m_{,1, 2}))=lm+4/5l for m≥4 and va(G(D_m_{, 2, 2}))=lm+1/5l+1 for any positive integer m=10q+j with j =0,1, 2, 3, 5, 6.

Key words: Integer distance graph, Vertex arboricity, Tree coloring

中图分类号:

05C70

左连翠, 崔玉泉, 刘家壮. 整数距离图G(D_{m, k,}₂)的点荫度[J]. 数学物理学报, 2010, 30(4): 968-983.

ZUO Lian-Cui, CUI Yu-Quan, LIU Jia-Zhuang. The Vertex Arboricity of Integer Distance Graphs G(D_{m, k}_{, 2})[J]. Acta mathematica scientia,Series A, 2010, 30(4): 968-983.

参考文献

[1] Akiyama J, Era H, Gerracio S V, Watanabe M. Path chromatic numbers of graphs. J Graph Theory, 1989, 13: 569--579

[2] Chang G J, Liu D D -F, Zhu X D. Distance graphs and $T$-coloring. J Combin Theory (Ser B), 1999, 75: 259--269

[3] Catlin P A, Lai H J. Vertex arboricity and maximum degree. Discrete Math, 1995, 141: 37--46

[4] Eggleton R B, Erdös P, Skilton D K. Colouring the real line. J Combin Theory (Ser B), 1985, 39: 86--100

[5] Eggleton R B, Erdös P, Skilton D K. Colouring prime distance graphs. Graphs and Combinatorics, 1990, 6: 17--32

[6] Goddard W. Acyclic coloring of planar graphs. Discrete Math, 1991, 91: 91--94

[7] Jörgensen L K. Vertex partitions of K_4,4-minor free graphs. Graphs and Combin, 2001, 17: 265--274

[8] Kemnitz A, Kolbery H. Coloring of integer distance graphs. Discrete Math, 1998, 191: 113--123

[9] Kemnitz A, Marangio M. Chromatic numbers of integer distance graphs. Discrete Math, 2001, 233: 239--246

[10] Liu D D -F, Zhu X D. Distance graphs with missing multiples in the distance sets. J Graph Theory, 1999, 30: 245--259

[11] Skrekovski R. On the critical point-arboricity graphs.J Graph Theory, 2002, 39: 50--61

[12] Voigt M, Walther H. Chromatic number of prime distance graphs. Discrete Applied Math, 1994, 51: 197--209

[13] Voigt M. Colouring of distance graphs. Ars Combin, 1999, 52: 3--12

[14] Matsumoto M. Bounds for the vertex linear arboricity. J Graph Theory, 1990, 14: 117--126

[15] Poh K. On the linear vertex-arboricity of a planar graph. J Graph Theory, 1990, 14: 73--75

[16] Zuo L C, Wu J L, Liu J Z. The vertex linear arboricity of an integer distance graph with a special distance set. Ars Combin, 2006, 79(2): 65--76

[17] Zuo L C, Wu J L, Liu J Z. The vertex linear arboricity of distance graphs. Discrete Math, 2006, 306(2): 284--289

[18] Zuo L C, Yu Q, Wu J L. Tree coloring of distance graphs with a real interval set. Applied Mathematics Letter, 2006, 19(12): 1341--1344

[19] Zuo L C, Wu J L, Liu J Z. The fractional vertex linear arboricity of graphs. Ars Combin, 2006, 81(5): 175--191

[20] 左连翠, 李霞. 整数距离图的点荫度. 山东大学学报(理学版), 2004, 39(2): 12--15

[21] 左连翠, 吴建良, 刘家壮. 整数距离图G(D_m,k,₂的点线性荫度. 系统科学与数学, 2006, 26(5): 522--532

[22] Yu Q, Zuo L C. The fractional vertex arboricity of graphs. Lecture Notes in Computer Science, 2007, 4381(1): 245--252

[23] Zuo L C, Yu Q, Wu J L. Vertex arboricity of integer distance graph G(D_m,_k). Discrete Math, 2009, 309(6): 1649--1657

[24] Zhang Zhongfu, Wang Weifan, et al. Edge-face chromatic number of 2-connected plane graphs with high maximum degree. Acta Mathematica Scientia, 2006, 26B(3): 477--482

整数距离图G(D_{m, k,}₂)的点荫度

The Vertex Arboricity of Integer Distance Graphs G(D_{m, k}_{, 2})

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

Metrics

本文评价

推荐阅读 10

[1]	辛永训;刘桂真. 重图的超f - 边覆盖染色[J]. 数学物理学报, 2008, 28(6): 1164-1172.
[2]	王骁力. 二分图中含有完美对集的2因子[J]. 数学物理学报, 2004, 24(4): 475-479.
[3]	欧见平, 张福基. 3限制边连通度与正则因子[J]. 数学物理学报, 2003, 23(6): 650-654.
[4]	颜谨. 图的有特殊性质的k-因子和半k-因子[J]. 数学物理学报, 2001, 21(zk): 676-682.