Incidence coloring of k-degenerated graphs

被引:37
作者
Dolama, MH
Sopena, É
Zhu, XD
机构
[1] Univ Bordeaux 1, LaBRI, F-33405 Talence, France
[2] Natl Sun Yat Sen Univ, Dept Appl Math, Kaohsiung 804, Taiwan
关键词
incidence coloring; k-degenerated graph; K-4-minor free graph; planar graph;
D O I
10.1016/j.disc.2004.01.015
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We prove that the incidence coloring number of every k-degenerated graph G is at most Delta(G) + 2k - 1. For K-4-minor free graphs (k = 2), we decrease this bound to Delta(G) + 2, which is tight. For planar graphs (k = 5), we decrease this bound to Delta(G) + 7. (C) 2004 Elsevier B.V. All rights reserved.
引用
收藏
页码:121 / 128
页数:8
相关论文
共 7 条