Article
Graphs Obtained from Collections of Blocks
Electronic Journal of Graph Theory and Applications
Document Type
Article
Publication Date
1-1-2015
DOI
10.5614/ejgta.2015.3.1.6
Disciplines
- Education and
- Mathematics
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
Citation Information
Colton Magnant, Pouria Salehi Nowbandegani and Hua Wang. "Graphs Obtained from Collections of Blocks" Electronic Journal of Graph Theory and Applications Vol. 3 Iss. 1 (2015) p. 50 - 55 ISSN: 2338-2287 Available at: http://works.bepress.com/hua_wang/96/
Electronic Journal of Graph Theory and Applications provides immediate open access to its content on the principle that making research freely available to the public supports a greater global exchange of knowledge. Full-text access to all papers is available for free.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.