On Coloring Box Graphs

Emilie Hogan, Joseph O’Rourke, Cindy Traub, Ellen Veomett

Research output: Contribution to journalArticlepeer-review


We consider the chromatic number of a family of graphs we call box graphs, which arise from a box complex in n-space. It is straightforward to show that any box graph in the plane has an admissible coloring with three colors, and that any box graph in n-space has an admissible coloring with n+1 colors. We show that for box graphs in n-space, if the lengths of the boxes in the corresponding box complex take on no more than two values from the set {1,2,3}, then the box graph is 3-colorable, and for some graphs three colors are required. We also show that box graphs in 3-space which do not have cycles of length four (which we call “string complexes”) are 3-colorable.

Original languageAmerican English
JournalDiscrete Mathematics
StatePublished - Feb 6 2015


  • Graph coloring
  • Box graph
  • Chromatic number


  • Mathematics

Cite this