Some results on the injective chromatic number of graphs

被引：24

作者：

Chen, Min ^{[1
]}

Hahn, Gena ^{[2
]}

Raspaud, Andre ^{[3
]}

Wang, Weifan ^{[1
]}

机构：

[1] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Peoples R China

[2] Univ Montreal, Dept Informat & Rech Operat, Montreal, PQ H3C 3J7, Canada

[3] Univ Bordeaux 1, LaBRI, CNRS, UMR 5800, F-33405 Talence, France

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2012年 / 24卷 / 03期

关键词：

Injective coloring; K-4-minor free graph; Planar graph; Maximum degree;

D O I：

10.1007/s10878-011-9386-2

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

A k-coloring of a graph G=(V,E) is a mapping c:V ->{1,2,aEuro broken vertical bar,k}. The coloring c is injective if, for every vertex vaV, all the neighbors of v are assigned with distinct colors. The injective chromatic number chi (i) (G) of G is the smallest k such that G has an injective k-coloring. In this paper, we prove that every K (4)-minor free graph G with maximum degree Delta a parts per thousand yen1 has . Moreover, some related results and open problems are given.

引用

页码：299 / 318

页数：20

共 12 条

[1]

Bondy J. A., 1976, Graduate Texts in Mathematics, V290

[2] Injective coloring of planar graphs [J].

Bu, Yuehua ;

Chen, Dong ;

Raspaud, Andre ;

Wang, Weifan .

DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) :663-672

[3] The L(2,1)-labeling problem on graphs [J].

Chang, GJ ;

Kuo, D .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1996, 9 (02) :309-316

[4] Some bounds on the injective chromatic number of graphs [J].

Doyon, Alain ;

Hahn, Gena ;

Raspaud, Andre .

DISCRETE MATHEMATICS, 2010, 310 (03) :585-590

[5] TOPOLOGY OF SERIES-PARALLEL NETWORKS [J].

DUFFIN, RJ .

JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 1965, 10 (02) :303-&

[6] On the L(p, 1)-labelling of graphs [J].

Goncalves, D. .

DISCRETE MATHEMATICS, 2008, 308 (08) :1405-1414

[7] LABELING GRAPHS WITH A CONDITION AT DISTANCE-2 [J].

GRIGGS, JR ;

YEH, RK .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1992, 5 (04) :586-595

[8] On the injective chromatic number of graphs [J].

Hahn, G ;

Kratochvíl, J ;

Sirán, J ;

Sotteau, D .

DISCRETE MATHEMATICS, 2002, 256 (1-2) :179-192

[9]

Havet F, 2008, PROCEEDINGS OF THE NINETEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P621

[10]

Kim S.J., 2009, preprint

← 1 2 →