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. |
Year | DOI | Venue |
---|---|---|
2015 | 10.5614/ejgta.2015.3.1.6 | ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS |
Keywords | Field | DocType |
block graph, chromatic number, diameter, hamiltonicity | Discrete mathematics,Block graph,Combinatorics,Vertex (geometry),Chromatic scale,Chordal graph,Windmill graph,Arbitrarily large,Mathematics,Hypercube,Bounded function | Journal |
Volume | Issue | ISSN |
3 | 1 | 2338-2287 |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Colton Magnant | 1 | 113 | 29.08 |
Pouria Salehi Nowbandegani | 2 | 5 | 4.30 |
Hua Wang | 3 | 1 | 1.06 |