期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

没有K_4-图子式的图的邻点可区别全染色 被引量：4

原文传递
导出
摘要 图G的邻点可区别全染色是G的一个正常全染色,使得每一对相邻顶点有不同的颜色集合.G的邻点可区别全色数χa(G)是使得G有一个k-邻点可区别全染色的最小的整数k.本文完整刻画了没有K4-图子式的图的邻点可区别全色数.证明了:如果G是一个满足最大度△≥3且没有K4-图子式的图,则△+1≤χa(G)≤△+2,且χa(G)=△+2当且仅当G中含有两个相邻最大度点.
作者 王维凡 王平
机构地区 浙江师范大学数学系 Department of Mathematics
出处 《中国科学（A辑）》 CSCD 北大核心 2009年第12期1462-1472,共11页 Science in China(Series A)
基金 国家自然科学基金(批准号:10771197) The James Chair at St.Francis Xavier University和Natural Sciencesand Engineering Research Council of Canada资助项目
关键词 邻点可区别全染色 没有K4-图子式的图 最大度
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献10

  • 1Zhang Z, Liu L, Wang J. Adjacent strong edge coloring of graphs. Appl Math Lett, 15:623-626 (2002).
  • 2Balister P N, Gyori E, Lehel J, et al. Adjacent vertex distinguishing edge-colorings. SIAM J Discrete Math, 21:237-250 (2007).
  • 3Hatami H. A △- 300 is a bound on the adjacent vertex distinguishing edge chromatic number. J Combin Theory Set B, 95:246 256 (2005).
  • 4Behzad M. Graphs and their chromatic numbers. PhD Thesis. Michigan: Michigan State University, 1965.
  • 5Vizing V. Some unsolved problems in graph theory (in Russian). Uspekhi Mat Nauk, 23:117-134 (1968).
  • 6张忠辅,陈祥恩,李敬文,姚兵,吕新忠,王建方.关于图的邻点可区别全染色[J].中国科学（A辑）,2004,34(5):574-583. 被引量：192
  • 7Chen X. On the adjacent vertex distinguishing total coloring numbers of graphs with A = 3. Discrete Math, 308:4003-4007 (2008).
  • 8Wang H. On the adjacent vertex distinguishing total chromatic number of the graphs with △(G) = 3. J Combin Optim, 14:87-109 (2007).
  • 9Wang Y, Wang W. Adjacent vertex distinguishing total colorings of outerplanar graphs. J Combin Optim, to appear.
  • 10Lih K-W, Wang W, Zhu X. Coloring the square of a K4-minor free graph. Discrete Math, 269:303-309 (2003).

二级参考文献8

  • 1Burris A C,Schelp R H.Vertex-distinguishing proper edge-colorings.J of Graph Theory,1997,26(2): 73-82
  • 2Bazgan C,Harkat-Benhamdine A,Li H,et al.On the vertex-distinguishing proper edge-coloring of graphs.J Combin Theory,Ser B,1999,75: 288-301
  • 3Balister P N,Bollobas B,Schelp R H.Vertex distinguishing colorings of graphs with △(G)=2.Discrete Mathematics,2002,252(2): 17-29
  • 4Zhang Zhongfu,Liu Linzhong,Wang Jianfang.Adjacent strong edge coloring of graphs.Applied Mathematics Letters,2002,15:623-626
  • 5Dietel Reinhard.Graph Theory.New York:Springer-Verlag,1997
  • 6Chartrand G,Lesniak-Foster L.Graph and Digraphs.2nd Edition.Monterey,CA: WadsworthBrooks/Cole,1986
  • 7Hansen P,Marcotte O.GraphColoring and Application.Providence: AMS,1999
  • 8Bondy J A,Murty U S R.Graph Theory with Applications.New York: American Elsevier,1976

共引文献191

同被引文献32

  • 1张忠辅,陈祥恩,李敬文,姚兵,吕新忠,王建方.关于图的邻点可区别全染色[J].中国科学（A辑）,2004,34(5):574-583. 被引量：192
  • 2陈祥恩,张忠辅.最大度不超过4的2-连通外平面图的邻点可区别全色数(英文)[J].兰州大学学报（自然科学版）,2006,42(6):96-102. 被引量：2
  • 3Alon N, Sudakov B, Zaks A. Acyclic edge colorings of graphs. J Graph Theory, 2001, 37:157-167.
  • 4Alon N, McDiarmid C, Reed B. Acyclic coloring of graphs. Random Struct Algor, 1991, 2:277- 288.
  • 5Molloy M, Reed B. Further algorithmic aspects of Lovasz local lemma. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, 524-529.
  • 6Muthu R, Narayanan N, Subramanian C R. Improved bounds on acyclic edge coloring. Electr Notes Discrete Math, 2005, 19:171-177.
  • 7Nesetril J, Wormald N C. The acyclic edge chromatic number of a random d-regular graph is d + 1. J Graph Theory, 2005, 49:69-74.
  • 8Alon N, Zaks A. Algorithmic aspects of acyclic edge coloring colorings. Algorithmica, 2002, 32:611-614.
  • 9Skulrattanakulchai S. Acyclic colorings of subcubic graphs. Inform Process Lett, 2004, 92:161-167.
  • 10Basavaraju M, Chandran L S, Cohen N, et al. Acyclic edge-colouring of planar graphs. SIAM J Discrete Math, 2011, 25:463-478.

引证文献4

二级引证文献15

中国科学（A辑）
2009年 第12期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部