PDF
Discussiones Mathematicae Graph Theory 31(1) (2011)
161-170
DOI: https://doi.org/10.7151/dmgt.1535
COLORING RECTANGULAR BLOCKS IN 3-SPACE
| Colton Magnant
Lehigh University | Daniel M. Martin
Universidade Federal do ABC |
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
Close