Coloring rectangular blocks in 3-space

• Autorzy: Colton Magnant , Daniel M. Martin
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

chromatic number; channel assignment problem; 3 dimensional rectangular blocks

Kategorie tematyczne

• 05C62: Graph representations (geometric and intersection representations, etc.) {For graph drawing, see also }
• 05C15: Coloring of graphs and hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2011
• Tom: 31
• Numer: 1
• Strony: 161-170

Daty

wydano

2011

otrzymano

2009-08-18

poprawiono

2010-04-22

zaakceptowano

2010-04-22

Twórcy

autor

Colton Magnant

• Lehigh University, Bethlehem PA, 18015, USA

autor

Daniel M. Martin

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

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgt.1535