SIMULTANEOUS COLORING OF EDGES AND FACES OF PLANE GRAPHS

被引：28

作者：

BORODIN, OV ^{[1
]}

机构：

[1] RUSSIAN ACAD SCI,INST MATH,NOVOSIBIRSK 630090,RUSSIA

来源：

DISCRETE MATHEMATICS | 1994年 / 128卷 / 1-3期

关键词：

D O I：

10.1016/0012-365X(94)90101-5

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The edges and faces of a plane graph are colored so that every two adjacent or incident of them are colored differently. The minimal number of colors for this kind of coloring is estimated. For the plane graphs of the maximal degree at least 10, the bound is the best possible. The proof is based on some new generalizations of Kotzig's Theorem on the minimal weight of edges in plane graphs. Another tool is the concept of assigned coloring (choosability).

引用

页码：21 / 33

页数：13

共 16 条

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

APPEL, K ;

HAKEN, W .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1976, 82 (05) :711-712

[2]

BEHZAD M, 1967, J LOND MATH SOC, V42, P226

[3]

Borodin O.V., 1987, METODY DISKRET ANALI, V45, P21

[4]

Borodin O.V., 1984, RUSSIAN METODY DISKR, V41, P12

[5]

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

[6]

FIAMCIK J, 1971, MAT CAS, V21, P9

[7]

JUCOVIC E, 1969, MAT CAS, V19, P225

[8]

KOSTOCHKA AV, 1979, 24TH INT WISS K TH I, P33

[9]

Kotzig A., 1955, MAT FYZ CASOPIS SLOV, V5, P101

[10]

Kronk H. V., 1973, Discrete Mathematics, V5, P253, DOI 10.1016/0012-365X(73)90142-8

← 1 2 →