共 50 条
(1,0,0)-Colorability of planar graphs without prescribed short cycles
被引:0
|作者:
Bu, Yuehua
[1
]
Xu, Jinghan
[1
]
Wang, Yingqian
[1
]
机构:
[1] Zhejiang Normal Univ, Coll Math Phys & Informat Engn, Jinhua 321004, Peoples R China
关键词:
Planar graph;
Steinberg conjecture;
Improper coloring;
Cycle;
LENGTH;
4;
D O I:
10.1007/s10878-013-9653-5
中图分类号:
TP39 [计算机的应用];
学科分类号:
081203 ;
0835 ;
摘要:
Let be non-negative integers. A graph is -colorable, if the vertex set of can be partitioned into subsets such that the subgraph induced by has maximum degree at most for . Let be the family of planar graphs with cycles of length neither 4 nor 8. In this paper, we prove that a planar graph in is -colorable if it has no cycle of length for some . Together with other known related results, this completes a neat conclusion on the -colorability of planar graphs without prescribed short cycles, more precisely, for every triple , planar graphs without cycles of length 4, or are -colorable whenever 4 < i < j <= 9.
引用
收藏
页码:627 / 646
页数:20
相关论文