Coloring the square of a K4-minor free graph

被引：61

作者：

Lih, KW

Wang, WF

Zhu, XD

机构：

[1] Acad Sinica, Inst Math, Taipei 115, Taiwan

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

[3] Natl Sun Yat Sen Univ, Dept Appl Math, Kaohsiung 804, Taiwan

来源：

DISCRETE MATHEMATICS | 2003年 / 269卷 / 1-3期

关键词：

series-parallel graph; K-4-minor free graph; square; chromatic number;

D O I：

10.1016/S0012-365X(03)00059-1

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be a K-4-minor free graph with maximum degree Delta. We prove that the chromatic number of the square of G is at most (i) Delta + 3 if 2 less than or equal to Delta less than or equal to 3; or (ii) [3Delta/2] + 1 if Delta greater than or equal to 4. Examples are given to show the bounds can be attained. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：303 / 309

页数：7

共 9 条

[1]

AGNARSSON G, 2000, UNPUB SIAM J DISCRET

[2]

BORODIN OV, 2001, ANAL ISSLED OPER 1, V8, P9

[3]

CHARTRAND G, 1967, ANN I H POINCARE B, V3, P433

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

DUFFIN, RJ .

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

[5]

MOLLOY M, 2002, BOUND CHROMATIC NUMB

[6]

Thomassen C, 2001, APPL TUTTE CYCLES

[7] Coloring the square of a planar graph [J].

van den Heuvel, J ;

McGuinness, S .

JOURNAL OF GRAPH THEORY, 2003, 42 (02) :110-124

[8]

WANG WF, IN PRESS SIAM J DISC

[9]

Wegner G, 1977, Graphs with given diameter and a coloring problem

← 1 →