Discussiones Mathematicae Graph Theory 31(1) (2011) 161-170
doi: 10.7151/dmgt.1535

[BIBTex] [PDF] [PS]

COLORING RECTANGULAR BLOCKS IN 3-SPACE

Colton Magnant

Lehigh University
Bethlehem PA, 18015, USA

Daniel M. Martin

Universidade Federal do ABC
Santo André, SP, CEP 09210-170, Brazil

Abstract

If rooms in an office building are allowed to be any rectangular solid, how many colors does it take to paint any configuration of rooms so that no two rooms sharing a wall or ceiling/floor get the same color? In this work, we provide a new construction which shows this number can be arbitrarily large.

Keywords: chromatic number, channel assignment problem, 3 dimensional rectangular blocks.

2010 Mathematics Subject Classification: Primary: 05C15;
Secondary: 05C62.

References

[1] J.P. Burling, On coloring problems of families of prototypes, Ph.D. Thesis - University of Colorado, 1, (1965).
[2] T.R. Jensen and B. Toft, Graph coloring problems, Wiley-Interscience Series in Discrete Mathematics and Optimization (John Wiley & Sons Inc., New York, 1995). A Wiley-Interscience Publication.
[3] A.V. Kostochka and J. Nesetril, Properties of Descartes' construction of triangle-free graphs with high chromatic number, Combin. Probab. Comput. 8 (1999) 467-472, doi: 10.1017/S0963548399004022.
[4] B. Reed and D. Allwright, Painting the office, MICS Journal 1 (2008) 1-8.

Received 18 August 2009
Revised 22 April 2010
Accepted 22 April 2010