共 50 条
Edge-choosability of planar graphs without non-induced 5-cycles
被引:9
|作者:
Cai, Jiansheng
[1
]
Hou, Jianfeng
[2
]
Zhang, Xia
[3
]
Liu, Guizhen
[2
]
机构:
[1] Weifang Univ, Sch Math & Informat Sci, Weifang 261061, Peoples R China
[2] Shandong Univ, Sch Math & Syst Sci, Jinan 250100, Peoples R China
[3] Shandong Normal Univ, Coll Math Sci, Jinan 250014, Peoples R China
基金:
中国国家自然科学基金;
关键词:
Planar graph;
Edge-coloring;
Choosability;
Cycle;
Chord;
Combinatorial problems;
LIST EDGE;
D O I:
10.1016/j.ipl.2008.12.001
中图分类号:
TP [自动化技术、计算机技术];
学科分类号:
0812 ;
摘要:
A graph G is edge-L-colorable, if for a given edge assignment L = {L(e): e is an element of E(G)}, there exits a proper edge-coloring phi of G such that phi(e) is an element of L(e) for all e is an element of E(G). If G is edge-L-colorable for every edge assignment L with vertical bar L(e)vertical bar >= k for e is an element of E(G), then G is said to be edge-k-choosable. In this paper, we prove that if G is a planar graph without non-induced 5-cycles, then G is edge-k-choosable, where k = max{7. Delta(G) + 1}. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码:343 / 346
页数:4
相关论文