Injective colorings of sparse graphs

被引：43

作者：

Cranston, Daniel W. ^{[3
,4
]}

Kim, Seog-Jin ^{[2
]}

Yu, Gexin ^{[1
]}

机构：

[1] Coll William & Mary, Williamsburg, VA 23185 USA

[2] Konkuk Univ, Seoul, South Korea

[3] Rutgers State Univ, DIMACS, Piscataway, NJ USA

[4] Virginia Commonwealth Univ, Richmond, VA USA

来源：

DISCRETE MATHEMATICS | 2010年 / 310卷 / 21期

基金：

美国国家科学基金会;

关键词：

Injective coloring; Maximum average degree; Planar graph; PLANAR GRAPHS; CHROMATIC NUMBER;

D O I：

10.1016/j.disc.2010.07.003

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let mad(G) denote the maximum average degree (over all subgraphs) of G and let chi(i)(G) denote the injective chromatic number of G. We prove that if mad(G) < 5/2, then chi(i)(C) <= Delta(G) + 1; and if mad(G) < 42/19, then chi(i)(C) = Delta(C). Suppose that G is a planar graph with girth g(G) and Delta(G) >= 4. We prove that if chi(i)(G) >= 9, then chi(i)(G) <= Delta(G) + 1; similarly, if g(G) >= 13, then chi(i)(C) = Delta(C). (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：2965 / 2973

页数：9

共 17 条

[1] The chromatic number of graph powers [J].

Alon, N ;

Mohar, B .

COMBINATORICS PROBABILITY & COMPUTING, 2002, 11 (01) :1-10

[2]

[Anonymous], 2001, Introduction to Graph Theory

[3] 2-distance (Δ+2)-coloring of planar graphs with girth six and Δ ≥ 18 [J].

Borodin, O. V. ;

Ivanova, A. O. .

DISCRETE MATHEMATICS, 2009, 309 (23-24) :6496-6502

[4]

Borodin O.V., 2007, DISKRETN ANAL ISSL 1, V14, P13

[5] List edge and list total colourings of multigraphs [J].

Borodin, OV ;

Kostochka, AV ;

Woodall, DR .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1997, 71 (02) :184-204

[6]

BORODIN OV, 1989, J REINE ANGEW MATH, V394, P180

[7]

BORODIN OV, 1979, THESIS NOVOSIBIRKS S

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

Bu, Yuehua ;

Chen, Dong ;

Raspaud, Andre ;

Wang, Weifan .

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

[9]

CRANSTON DW, ALGORITHMIC IN PRESS, DOI DOI 10.1007/S00453-010-9425-X)

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

Doyon, Alain ;

Hahn, Gena ;

Raspaud, Andre .

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

← 1 2 →