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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1535,
author = {Colton Magnant and Daniel M. Martin},
title = {Coloring rectangular blocks in 3-space},
journal = {Discussiones Mathematicae Graph Theory},
volume = {31},
year = {2011},
pages = {161-170},
zbl = {1284.05105},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1535}
}
Colton Magnant; Daniel M. Martin. Coloring rectangular blocks in 3-space. Discussiones Mathematicae Graph Theory, Tome 31 (2011) pp. 161-170. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1535/
[000] [1] J.P. Burling, On coloring problems of families of prototypes, Ph.D. Thesis - University of Colorado, 1, (1965)
[001] [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.
[002] [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. | Zbl 0951.05036
[003] [4] B. Reed and D. Allwright, Painting the office, MICS Journal 1 (2008) 1-8.