Two floor building needing eight colors

2014/05/26 by Stéphane Bessy, Bessy, Stéphane, Daniel Gonçalves +4
Mathematics · Physics and Astronomy · Psychology · #05C15 #Color Science and Applications #Color perception and design #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15

paper · pdf · doi:10.48550/arxiv.1405.6620

arxiv created 2014/05/26 · openalex publication_date 2014/05/26 · arxiv updated 2014/05/27 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

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

Related

• A sequel to the adventure of RGB-tilings to explore the Four Color Theorem
• The chromatic number of 4-dimensional lattices
• 3-Colouring Planar Graphs
• Algorithmic methods of finite discrete structures. The Four Color Theorem. Theory, methods, algorithms
• Chromatic numbers for contact graphs of congruent cuboids