Two-floor buildings need eight colors

DOI10.7155/JGAA.00344zbMATH Open1306.05052OpenAlexW2053069614MaRDI QIDQ2940593FDOQ2940593

Authors Stéphane Bessy, Daniel Gonçalves, Jean-Sébastien Sereni 

Publication date 27 January 2015

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.6620

zbMATH Keywords

chromatic number3-dimensional parallelepipeds

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: Motivated by frequency assignment in office blocks, we study the chromatic number of the adjacency graph of $3$-dimensional parallelepiped arrangements. 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$ colours. 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 or volume).

Recommendations

• Coloring rectangular blocks in 3-space
• On coloring box graphs
• The chromatic number of the plane: the bounded case
• On corners of objects built from parallelepiped bricks
• Publication:3203045

Cited in

(3)

• On corners of objects built from parallelepiped bricks
• Coloring rectangular blocks in 3-space
• Chromatic number of regular walls.

This page was built for publication: Two-floor buildings need eight colors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2940593)