Journal of Graph Algorithms and Applications
|Home||Issues||About JGAA||Instructions for Authors|
Two-floor buildings need eight colors
Vol. 19, no. 1, pp. 1-9, 2015. Regular paper.
Abstract Motivated by frequency assignment in office blocks, we study the chromatic number of the adjacency graph of a 3-dimensional parallelepiped arrangement. In the case each parallelepiped is within one floor, a direct application of the Four-Colour Theorem yields that the adjacency graph has chromatic number at most 8. We provide an example of such an arrangement needing exactly 8 colors. We also discuss bounds on the chromatic number of the adjacency graph of general arrangements of 3-dimensional parallelepipeds according to geometrical measures of the parallelepipeds (side length, total surface area or volume).
Submitted: May 2014.
Reviewed: August 2014.
Revised: September 2014.
Accepted: December 2014.
Final: January 2015.
Published: January 2015.
Communicated by Joseph S. B. Mitchell