Graphs Obtained from Collections of Blocks

Colton Magnant, Pouria Salehi Nowbandegani, Hua Wang

Research output: Contribution to journalArticlepeer-review

Abstract

Given a collection of d-dimensional rectangular solids called blocks, no two of which sharing interior points, construct a block graph by adding a vertex for each block and an edge if the faces of the two corresponding blocks intersect nontrivially. It is known that if d ≥ 3, such block graphs can have arbitrarily large chromatic number. We prove that the chromatic number can be bounded with only a mild restriction on the sizes of the blocks. We also show that block graphs of block configurations arising from partitions of d-dimensional hypercubes into sub-hypercubes are at least d-connected. Bounds on the diameter and the hamiltonicity of such block graphs are also discussed

Original languageAmerican English
JournalElectronic Journal of Graph Theory and Applications
Volume3
DOIs
StatePublished - Jan 1 2015

Keywords

  • Block graph
  • Chromatic number
  • Diameter
  • Hamiltonicity

DC Disciplines

  • Education
  • Mathematics

Fingerprint

Dive into the research topics of 'Graphs Obtained from Collections of Blocks'. Together they form a unique fingerprint.

Cite this