Coloring graphs with crossings

被引：7

作者：

Oporowski, Bogdan ^{[1
]}

Zhao, David ^{[2
]}

机构：

[1] Louisiana State Univ, Dept Math, Baton Rouge, LA 70803 USA

[2] Univ Texas Austin, Dept Comp Sci, Austin, TX 78712 USA

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 09期

关键词：

Chromatic number; Clique number; Crossing number; Immersion;

D O I：

10.1016/j.disc.2008.07.040

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We generalize the Five-Color Theorem by showing that it extends to graphs with two crossings. Furthermore, we show that if a graph has three crossings, but does not contain K(6) as a subgraph, then it is also 5-colorable. We also consider the question of whether the result can be extended to graphs with more crossings. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：2948 / 2951

页数：4