ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


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


Colton Magnant

Lehigh University
Bethlehem PA, 18015, USA

Daniel M. Martin

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


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.


[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