Coloring Plane Graphs with Independent Crossings

被引：38

作者：

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
Borodin, OV
Sanders, DP
Zhao, Y
[J]. DISCRETE MATHEMATICS, 1999, 203 (1-3) : 23 - 40
[7] CYCLIC COLORING OF PLANE GRAPHS
BORODIN, OV
[J]. DISCRETE MATHEMATICS, 1992, 100 (1-3) : 281 - 289
[8] A NEW PROOF OF THE 6 COLOR THEOREM
BORODIN, OV
[J]. 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
Enomoto, H
Hornák, M
Jendrol, S
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2001, 14 (01) : 121 - 137

← 1 2 3 →