Coloring Plane Graphs with Independent Crossings

被引：41

作者：

Kral, Daniel ^{[1
]}

Stacho, Ladislav ^{[2
]}

机构：

[1] Charles Univ Prague, Fac Math & Phys, Inst Theoret Comp Sci ITI, Prague 11800, Czech Republic

[2] Simon Fraser Univ, Dept Math, Burnaby, BC V5A 1S6, Canada

来源：

JOURNAL OF GRAPH THEORY | 2010年 / 64卷 / 03期

基金：

加拿大自然科学与工程研究理事会;

关键词：

planar graphs; cyclic coloring; crossing number; chromatic number; CYCLIC COLORINGS; FACIAL COLORINGS; THEOREM;

D O I：

10.1002/jgt.20448

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that every plane graph with maximum face size four in which all faces of size four are vertex-disjoint is cyclically 5-colorable. This answers a question of Albertson whether graphs drawn in the plane with all crossings independent are 5-colorable. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 64: 184-205. 2010

引用

页码：184 / 205

页数：22

共 25 条

[1]

Albertson M., 2008, SIAM C DISCR MATH BU

[2]

Albertson MO, 2008, ARS MATH CONTEMP, V1, P1

[3]

AMINI O, UNIFIED APPROA UNPUB

[4]

Appel K., 1976, B AM MATH SOC, V82, P449

[5]

AZARIJA J, ARXIV08112704

[6] On cyclic colorings and their generalizations [J].

Borodin, OV ;

Sanders, DP ;

Zhao, Y .

DISCRETE MATHEMATICS, 1999, 203 (1-3) :23-40

[7] CYCLIC COLORING OF PLANE GRAPHS [J].

BORODIN, OV .

DISCRETE MATHEMATICS, 1992, 100 (1-3) :281-289

[8] A NEW PROOF OF THE 6 COLOR THEOREM [J].

BORODIN, OV .

JOURNAL OF GRAPH THEORY, 1995, 19 (04) :507-521

[9]

BORODIN OV, 1984, METODY DISKRET ANAL, V41, P12

[10] Cyclic chromatic number of 3-connected plane graphs [J].

Enomoto, H ;

Hornák, M ;

Jendrol, S .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2001, 14 (01) :121-137

← 1 2 3 →