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

不含特殊短圈平面图的无圈边染色 被引量：1

Acyclic edge coloring of planar graphs without cycles of specific lengths
下载PDF
导出
摘要 无圈边染色是指图G的一个正常边染色,使其不产生双色圈.研究了不含特殊短圈平面图的无圈边染色问题,证明了:如果平面图G不含4到8-圈,那么G的无圈边染色数不大于Δ(G)+1. A proper edge coloring of a graph G is called acyclic if there are no bicolored cycles in G.It was proved that every planar graph without cycles of lengths 4 to 8 was acyclic（Δ（G）＋1）-edge colorable.
作者 郑丽娜
机构地区 浙江师范大学数理与信息工程学院
出处 《浙江师范大学学报（自然科学版）》 CAS 2012年第1期32-36,共5页 Journal of Zhejiang Normal University:Natural Sciences
关键词 平面图 圈 无圈边染色 无圈边色数 planar graph cycle acyclic edge coloring acyclic edge chromatic number
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献10

  • 1Fiam6ik I. The acyclic chromatic class of a graph [ J ]. Math Slovaca, 1978 28 ( 3 ) : 139-145.
  • 2Alon N, McDiarmid C, Reed B. Acyclic coloring of graphs [ J ]. Random Structures Algorithms, 1991,2 (3) :277-288.
  • 3Molloy M, Reed B. Further algorithmic aspects of Lovtsz local lemma [ C ]//Proceedings of the 30th Annual ACM Symposium on Theory of Computing held in Dallas. Dallas : ACM, 1998:524-529.
  • 4Muthu R. N aravanan N. Subramanian C R. Imoroved bounds on acvclic edge coloring[ J ]. Discrete Math ,2007,307 (23) :3063-3069.
  • 5Alon N, Sudakov B, Zaks A. Acyclic edge colorings of graphs[ J ]. Graph Theory ,2001,37 (3) :157-167.
  • 6Alon N, Zaks A. Algorithmic aspects of acyclic edge coloring [ J ]. Algorithmica, 2002,32 ( 4 ) :611-61 g.
  • 7Cohen N, Havet F, Mtiller T. Acyclic edge-colouring of planar graphs, Extended abstract [ J ]. Eletronic Notes in Discrete Math, 2009,34 ( 5 ) : 417-421.
  • 8Sun Xiangyong, Wu Jianliang. Acyclic edge colorings of planar graphs without short cycles[ C ]//Proceedings of the 7th International Symposium on Operations Research and Its Applications held in Lijiang. Lijiang:APORC&CAS,2008:325-329.
  • 9Hou Jianfeng, Liu Guizhen, Wu Jianliang. Acyclic edge coloring of planar graphs without small cycles [ J ]. Graphs andCombinatorics, 2011 : 10. 1007/s00373-011-1043-0.
  • 10Gao Yunshu, Yu Dongxiao. Acyclic edge coloring of planar graphs without cycles of specific lengths [ J ]. Appl Math Comput, 2011,37 (2) : 533-540.

同被引文献3

引证文献1

浙江师范大学学报（自然科学版）
2012年 第1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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