Graphs Obtained From Collections of Blocks
2015  //  DOI: 10.5614/ejgta.2015.3.1.6
Colton Magnant, Pouria Salehi Nowbandegani, Hua Wang

Metrik

  • Eye Icon 153 kali dilihat
  • Download Icon 45 downloads
Metrics Icon 153 kali dilihat  //  45 downloads
Graphs Obtained From Collections of Blocks Image
Abstrak

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 \geq 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.

Full text
Show more arrow
 

Metrik

  • Eye Icon 153 kali dilihat
  • Download Icon 45 downloads
Metrics Icon 153 kali dilihat  //  45 downloads