Injective Colorings of Graphs with Low Average Degree

被引：36

作者：

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

Kim, Seog-Jin ^{[1
]}

Yu, Gexin ^{[4
]}

机构：

[1] Konkuk Univ, Seoul, South Korea

[2] Virginia Commonwealth Univ, Dept Math & Appl Math, Richmond, VA USA

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

[4] Coll William & Mary, Williamsburg, VA USA

来源：

ALGORITHMICA | 2011年 / 60卷 / 03期

基金：

美国国家科学基金会;

关键词：

Injective coloring; Discharging method; Maximum average degree; List coloring; CHROMATIC NUMBER; PLANAR GRAPHS; SQUARE; THEOREM;

D O I：

10.1007/s00453-010-9425-x

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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 Delta >= 4 and mad (G) < 14/5, then chi i (G) <= Delta +2. When Delta = 3, we show that mad (G) < 36/13 implies chi i (G) <= 5. In contrast, we give a graph G with Delta = 3, mad (G) = 36/13, and chi (i) (G)=6.

引用

页码：553 / 568

页数：16

共 20 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[2]

Borodin O.V., 1990, Mat. Zametki, V48, P22

[3] 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

[4]

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

[5] The strong perfect graph theorem [J].

Chudnovsky, Maria ;

Robertson, Neil ;

Seymour, Paul ;

Thomas, Robin .

ANNALS OF MATHEMATICS, 2006, 164 (01) :51-229

[6]

Cornuejols G., 2003, Optima, V70, P2

[7] List-coloring the square of a subcubic graph [J].

Cranston, Daniel W. ;

Kim, Seog-Jin .

JOURNAL OF GRAPH THEORY, 2008, 57 (01) :65-87

[8]

CRANSTON DW, DISCRETE MA IN PRESS

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

Doyon, Alain ;

Hahn, Gena ;

Raspaud, Andre .

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

[10]

Erdos P., 1979, P W COAST C COMB GRA, P125

← 1 2 →