图着色下的树顶点邻集的行为

数学物理学报 ›› 2011, Vol. 31 ›› Issue (2): 567-576.

图着色下的树顶点邻集的行为

姚兵¹|程辉¹|姚明²|张忠辅^1,3

1.西北师范大学数学与信息科学学院兰州 730070|2.兰州石化职业技术学院信息处理与控制工程系兰州 730060|3.兰州交通大学应用数学研究所兰州 730070

收稿日期:2008-10-08 修回日期:2010-09-05 出版日期:2011-04-25 发布日期:2011-04-25
基金资助:
国家自然科学基金(10771091)和西北师范大学科技创新工程(NWNU-KJCXGC-03-18)资助

Behaviors of Vertex Neighbors of Trees Under Some Graph Colorings

YAO Bing¹, CHENG Hui¹, YAO Meng², ZHANG Zhong-Fu^1,3

1.College of Mathematics and Information Science, Northwest Normal University, Lanzhou 730070|2.Department of Information Process and Control Engineering, Lanzhou Petrochemical College of Vocational Technology, Lanzhou 730060|3.Institute of Applied Mathematics, Lanzhou Jiaotong University, Lanzhou 730070

Received:2008-10-08 Revised:2010-09-05 Online:2011-04-25 Published:2011-04-25
Supported by:
国家自然科学基金(10771091)和西北师范大学科技创新工程(NWNU-KJCXGC-03-18)资助

摘要/Abstract

摘要：

图着色下的树顶点邻集的行为展示了有趣的问题.该文证明了树顶点邻集的行为对一些图全着色有着非常强的性质,或多或少地揭示了树顶点邻集的行为与着色猜想的一些关系.作者期望应用这种邻集的行为去深刻地研究图着色问题.

关键词: 图着色, 可区分着色, 树

Abstract:

Behaviors of vertex neighbors of trees under certain graph colorings show some interesting problems. These behaviors of vertex neighbors of trees give stronger properties for known total colorings, and reveal some relations between the coloring conjectures, more or less. It is hoped to apply these behaviors to study deeply graph coloring problems.

Key words: Graph colorings, Distinguishing colorings, Trees

中图分类号:

05C15

姚兵, 程辉, 姚明, 张忠辅. 图着色下的树顶点邻集的行为[J]. 数学物理学报, 2011, 31(2): 567-576.

YAO Bing, CHENG Hui, YAO Meng, ZHANG Zhong-Fu. Behaviors of Vertex Neighbors of Trees Under Some Graph Colorings[J]. Acta mathematica scientia,Series A, 2011, 31(2): 567-576.

参考文献

[1] Balister P N, Bollobàs Béla, Schelp R H. Vertex-distinguishing colorings of graphs with Δ(G)=2. Discrete Mathmatics, 2002, 252(1-3): 17--29

[2] Bollobàs Béla. The Modern Graph Theory. New York: Springer-Verlag, 1998

[3] Bondy J A, Murty U S R. Graph Theory with Application. New York: Macmillan, 1976

[4] Burris A C. Vertex-distinguishing edge-colorings[D]. Dissertation, Memphis State University, 1993

[5] Burris A C, Schelp R H. Vertex-distinguishing proper edge-coloring.Journal of Graph Theory, 1997, 26(2): 70--82

[6] Garey M R, Johnson D S. Computers and Intractability. New York: W H Freeman, 1979

[7] Joseph A. Gallian. A dynamic survey of graph labeling. Electronic Journal of Combinatorics, 2007, 14: DS6

[8] Hamed Hatami. Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number. Journal of Combinatorial Theory (Series B), 2005, 95: 246--256

[9] Guizhen Liu, Lanju Zhang. Properties of fractional k-factor of graphs. Acta Mathematica Scientia, 2005, 25B(2): 301--304

[10] Hongmei Liu. Circular chromatic number and mycielski graphs. Acta Mathematica Scientia, 2006, 26B(2): 314--320

[11] Michael Molloy, Bruce Reed. Graph Colouring and the Probabilistic Method. Berlin, Heidelberg: Springer-Verlag, 2002

[12] Huimin Song, Guizhen Liu. On f-edge cover-coloring of simple graphs. Acta Mathematica Scientia, 2005, 25B(1): 145--151

[13] Weifan Wang, Kemin Zhang. Entire chromatic number and Δ-matching of outerplane graphs. Acta Mathematica Scientia, 2005, 25B(4): 672--680

[14] Ming Yao, Bing Yao. A note on the definition of a tree. The Proceeding of the 2nd International Conference on Biomedical Engineering and Informatics, IEEE (USA), 2009: 2137--2141

[15] Bing Yao, Zhongfu Zhang, Ming Yao. A class of spanning trees. International Journal of Computer, Mathematical Sciences and Applications, 2007, 1(2-4): 191--198

[16] Zhongfu Zhang, Linzhong Liu, Jianfang Wang. Adjacent strong edge coloring of graphs. Applied Mathematics Letters, 2002, 15: 623--626

[17] Zhongfu Zhang, Xiang'en Chen, Jingwen Li, Bing Yao, Xinzhong Lu. On the adjacent vertex distinguishing total coloring of graphs. Science In China (Series A), 2005, 48(3): 289--299

[18] Zhongfu Zhang, Weifan Wang, Jingwen Li, Bing Yao, Yuehua Bu. Edge-face chromatic number of 2-connected plane graphs with high maximum degree. Acta Mathematica Scientia, 2006, 26B(3): 477--482

[19] Zhongfu Zhang, Hui Cheng, Bing Yao, Jingwen Li, Xiangen Chen, Baogeng Xu. On the adjacent-vertex strong-distinguishing total coloring of graphs. Science in China (Series A), 2008, 51(3): 427--436

[20] 李永训, 刘桂真. 重图的超f -边覆盖染色. Acta Mathematica Scientia, 2008, 28A(3): 1164--1172