Two floor building needing eight colors

Stéphane Bessy (1) , Daniel Gonçalves (1) , Jean-Sébastien Sereni (2)

1 ALGCO - Algorithmes, Graphes et Combinatoire
2 ORPAILLEUR - Knowledge representation, reasonning

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).

Mots clés: graph colouring; parallelepiped arrangements; cuboids; adjacency; WLAN

Domaines: Combinatoire [math.CO]

Stéphane Bessy, Daniel Gonçalves, Jean-Sébastien Sereni. Two floor building needing eight colors. Journal of Graph Algorithms and Applications, 2015, 19 (1), pp.1--9. ⟨10.7155/jgaa.00344⟩. ⟨hal-00996709v2⟩