期刊文献+

平面图的无圈边染色

Acyclic Edge Colouring of Pianar Graphs
下载PDF
导出
摘要 利用差值转移的方法证明了,如果g(G)≥4则有X′a≤Δ(G)+4.图G=(V,E)是简单图,映射C:E→[k],被称作是图G的一个无圈k边染色.如果任意相邻的两个边染有不同的颜色,以及图G中不含有2-色圈,换句话说即图G中任何染两种颜色的边的导出子图是一棵森林. Let G=(V,E) be any finite graph.A mapping C:E→[k]is called an acyclic edge colouring of G,if any two adjacent edges have different colours and there are no bichromatic cycles in G.In other words,the subgraph induced by the union of any two colour classes is a forest.The minimum number k of colours,such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G,denoted by X′a(G).Alon et al.conjectured that for any graph G it holds that X′a(G)≤Δ(G)+2;here Δ(G) stands for the maximum degree of G.In this paper weprove the planar graphs with girth at least 4,then X′a≤Δ(G)+4.
作者 段娟娟 丁伟
出处 《淮阴师范学院学报(自然科学版)》 CAS 2011年第5期393-398,共6页 Journal of Huaiyin Teachers College;Natural Science Edition
基金 中央高校基本科研业务费专项基金资助项目(2010LKSX06)
关键词 无圈染色 平面图 围长 最大平均度 acyclic chromatic index planeproblems girth maximum average degree
  • 相关文献

参考文献12

  • 1West D B. Tntroduction to Graph Theory [ M]. Prentice Hall, Upper Saddle River, 2001. 被引量:1
  • 2Alon N, Sudakov, Zaks A. Acycle coloring of graphs [ J]. J GraphTheory, 2001,37:157 - 167. 被引量:1
  • 3Alon N, McDiarmid C J H, Reed B A. Acycli coloring of graphs [J]. Random Structures Algorithms, 1991,2:277- 288. 被引量:1
  • 4Basavaraju, Chandran L S. Acyclecoloring of subcubic graphs [J].Discrete Math, 2008,308: 6650- 6653. 被引量:1
  • 5Fiedorowiez A, Haluszezak M, Naraynan N. About acyclie edge colourings of planar graphs [ J]. Tnform Process Lett, 2008,108: 412 - 417. 被引量:1
  • 6Mieczyslaw, Borowiecki, Anna. Fiedorowicz, Acyclic dege colouring of planar graphsWithout short cycles [ J]. Tn Faculty of Mathematic, Computer Science and Econometrics, University of Zielona Gora, Z, Szafrana 4a: 65 - 516. 被引量:1
  • 7Wei D, Xu B B. Some results on acyclic edge coloring of piane graphs [J]. Information Processing Letters, 2010,110:887 - 892. 被引量:1
  • 8Montassier M, Ochem P, Raspaud A. On the acyclic choosability of graphs [J] .J. Graph Theory,2006,51:281 - 300. 被引量:1
  • 9Molloy M, Reed B. Futher algorithmic aspects of the local lemma [J]. Tn Proceedings of the 30thAnnual ACM Symposium on Theoy of Computing, 1998: 524 - 529. 被引量:1
  • 10Muthu R, Narayanan , Subramanian C R. Optimal aeycle edge eolouring of grid like graphs [ J]. TnComputing and Combinatories, 12th COCOON, Taipei, Taiwan, 2006,4508:144 - 152. 被引量:1

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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