On coloring box graphs

被引：0

作者：

Hogan, Emilie ^{[1
]}

O'Rourke, Joseph ^{[2
]}

Traub, Cindy ^{[3
]}

Veomett, Ellen ^{[4
]}

机构：

[1] Pacific NW Natl Lab, Richland, WA 99352 USA

[2] Smith Coll, Northampton, MA 01063 USA

[3] So Illinois Univ Edwardsville, Chicago, IL USA

[4] St Marys Coll Calif, New York, NY 10020 USA

来源：

DISCRETE MATHEMATICS | 2015年 / 338卷 / 02期

基金：

美国国家科学基金会;

关键词：

Graph coloring; Box graph; Chromatic number; MAP;

D O I：

10.1016/j.disc.2014.09.004

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We consider the chromatic number of a family of graphs we call box graphs, which arise from a box complex in n-space. It is straightforward to show that any box graph in the plane has an admissible coloring with three colors, and that any box graph in n-space has an admissible coloring with n + 1 colors. We show that for box graphs in n-space, if the lengths of the boxes in the corresponding box complex take on no more than two values from the set {1, 2, 3}, then the box graph is 3-colorable, and for some graphs three colors are required. We also show that box graphs in 3-space which do not have cycles of length four (which we call "string complexes") are 3-colorable. (C) 2014 Elsevier B.V. All rights reserved.

引用

页码：209 / 216

页数：8

共 8 条

[1]

[Anonymous], GEOMBINATORICS

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