Coloring the square of a planar graph

被引：137

作者：

van den Heuvel, J

McGuinness, S

机构：

[1] Univ London London Sch Econ & Polit Sci, Ctr Discrete & Applicable Math, Dept Math, London WC2A 2AE, England

[2] Umea Univ, Dept Math, S-90187 Umea, Sweden

来源：

JOURNAL OF GRAPH THEORY | 2003年 / 42卷 / 02期

关键词：

planar graph; chromatic number; labeling of a graph;

D O I：

10.1002/jgt.10077

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that for any planar graph G with maximum degree Delta, it holds that the chromatic number of the square of G satisfies chi(G(2)) less than or equal to 2Delta + 25. We generalize this result to integer labelings of planar graphs involving constraints on distances one and two in the graph. (C) 2002 Wiley Periodicals, Inc.

引用

页码：110 / 124

页数：15

共 17 条

[1]

AGNARSSON G, 2000, COLORING POWERS PLAN

[2] EVERY PLANAR MAP IS 4 COLORABLE .1. DISCHARGING [J].

APPEL, K ;

HAKEN, W .

ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) :429-490

[3] EVERY PLANAR MAP IS 4 COLORABLE .2. REDUCIBILITY [J].

APPEL, K ;

HAKEN, W ;

KOCH, J .

ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) :491-567

[4]

BORODIN OV, 2001, DISKRETN ANAL ISSL 1, V8, P9

[5]

BORODIN OV, 2001, DISKRETN ANAL ISSLED, V8, P15

[6] On L(d, 1)-labelings of graphs [J].

Chang, GJ ;

Ke, WT ;

Kuo, D ;

Liu, DDF ;

Yeh, RK .

DISCRETE MATHEMATICS, 2000, 220 (1-3) :57-66

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

Chang, GJ ;

Kuo, D .

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

[8]

Georges J., 1995, CONGR NUMER CONF J N, V109, P141

[9]

Georges JP, 1996, J GRAPH THEOR, V22, P47

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

GRIGGS, JR ;

YEH, RK .

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

← 1 2 →