Some results on the incidence coloring number of a graph

被引：15

作者：

Wu, Jiaojiao ^{[1
]}

机构：

[1] Natl Taiwan Univ, Dept Math, Taipei, Taiwan

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 12期

关键词：

Incidence coloring; The square of graphs; Cubic graphs; STAR ARBORICITY;

D O I：

10.1016/j.disc.2008.10.027

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

This paper proves that if G is a cubic graph which has a Hamiltonian path or G is a bridgeless Cubic graph of large girth, then its incidence coloring number is at most 5. By relating the incidence coloring number of a graph G to the chromatic number of G(2), we present simple proofs of some known results, and characterize regular graphs G whose incidence coloring number equals Delta(G) + 1. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：3866 / 3870

页数：5

共 9 条

[1] THE STAR ARBORICITY OF GRAPHS
ALGOR, I
ALON, N
[J]. DISCRETE MATHEMATICS, 1989, 75 (1-3) : 11 - 22
[2] ALON JHN, 2000, PROBABILISTIC METHOD, P70
[3] INCIDENCE AND STRONG EDGE COLORINGS OF GRAPHS
BRUALDI, RA
MASSEY, JJQ
[J]. DISCRETE MATHEMATICS, 1993, 122 (1-3) : 51 - 58
[4] Incidence coloring of k-degenerated graphs
Dolama, MH
Sopena, É
Zhu, XD
[J]. DISCRETE MATHEMATICS, 2004, 283 (1-3) : 121 - 128
[5] On incidence coloring and star arboricity of graphs
Guiduli, B
[J]. DISCRETE MATHEMATICS, 1997, 163 (1-3) : 275 - 278
[6] Petersen J., 1891, ACTA MATH, V15, P193, DOI [10.1007/BF02392606, DOI 10.1007/BF02392606]
[7] On incidence coloring for some cubic graphs
Shiu, WC
Lam, PCB
Chen, DL
[J]. DISCRETE MATHEMATICS, 2002, 252 (1-3) : 259 - 266
[8] The incidence coloring number of Halin graphs and outerplanar graphs
Wang, SD
Chen, DL
Pang, SC
[J]. DISCRETE MATHEMATICS, 2002, 256 (1-2) : 397 - 405
[9] Labeling planar graphs with conditions on girth and distance two
Wang, WF
Lih, KW
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2003, 17 (02) : 264 - 275

← 1 →