ACYCLIC COLORINGS OF PLANAR GRAPHS

被引：235
作者：
BORODIN, OV
机构：
[1] Institute of Mathematics, Siberian Branch, The U.S.S.R. Academy of Sciences, Novosibirsk -90
来源：
DISCRETE MATHEMATICS | 1979年 / 25卷 / 03期
关键词：
D O I：
10.1016/0012-365X(79)90077-3
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
The conjecture of B. Grünbaum on existing of admissible vertex coloring of every planar graph with 5 colors, in which every bichromatic subgraph is acyclic, is proved and some corollaries of this result are discussed in the present paper. © 1979.
引用
收藏
页码：211 / 236
页数：26
相关论文
共 12 条
[1]   EVERY PLANAR GRAPH HAS AN ACYCLIC-7-COLORING [J].
ALBERTSON, MO ;
BERMAN, DM .
ISRAEL JOURNAL OF MATHEMATICS, 1977, 28 (1-2) :169-174
[2]  
Borodin O.V., 1976, DISKRETNY ANALIZ, V28, P3
[3]  
Chartrand G., 1971, J COMB THEORY B, V10, P12
[4]  
CHARTRAND G, 1968, J LONDON MATH SOC, V44, P612
[5]   ACYCLIC COLORINGS OF PLANAR GRAPHS [J].
GRUNBAUM, B .
ISRAEL JOURNAL OF MATHEMATICS, 1973, 14 (04) :390-408
[6]   ON PARTITIONING PLANAR GRAPHS [J].
HEDETNIEMI, S .
CANADIAN MATHEMATICAL BULLETIN, 1968, 11 (02) :203-+
[7]  
Kostochka A.V., 1976, DISCRETNY ANAL, V28, P40
[8]   PAPER OF GRUNBAUM ON ACYCLIC COLORINGS [J].
KOSTOCHKA, AV ;
MELNIKOV, LS .
DISCRETE MATHEMATICS, 1976, 14 (04) :403-406
[9]  
LICK DR, 1969, J LOND MATH SOC, V1, P750
[10]   EVERY PLANAR GRAPH HAS AN ACYCLIC 8-COLORING [J].
MITCHEM, J .
DUKE MATHEMATICAL JOURNAL, 1974, 41 (157) :177-181
12