Colton Magnant, Pouria Salehi Nowbandegani, Hua Wang

Department of Mathematical Sciences, Georgia Southern University, Statesboro, GA, USA.

cmagnant@georgiasouthern.edu, pouria.salehi@gmail.com, hwang@georgiasouthern.edu

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.

Keywords: block graph, chromatic number, diameter, hamiltonicity

Mathematics Subject Classification : 05C15

DOI: 10.5614/ejgta.2015.3.1.6

1. Introduction

In this work, we consider properties of graphs obtained from collections of rectangular solids. In a d-dimensional space, define a block to be the product of d closed intervals, one in each dimension. If d = 2, blocks are rectangles while if d = 3, blocks are rectangular solids. A set of blocks is called valid if no two blocks have d-dimensional intersection. All sets of blocks considered in this work are valid. Two blocks are said to be touching if they have nontrivial (d − 1)-dimensional intersection. Given a collection of blocks D, define the block graph of D to be the graph G = G(D) containing a vertex for each block and an edge if the corresponding pair of blocks are touching. All standard graph terminology can be found in [1].

Received: 19 June 2014, Revised: 16 February 2015, Accepted: 14 March 2015.

When d = 2, block graphs are planar so the chromatic number is at most 4 by the four color theorem. The chromatic number of block graphs when d = 3 was studied in [2, 3] where it was proven that there exist block collections D^k with χ(G(D)) = k for any positive integer k, contradicting the intuition that these block graphs behave in a manner similar to planar graphs. Both proofs are constructive and make use of blocks that are very large in one dimension and small in the other two. If this tool is forbidden, it turns out that the chromatic number is bounded as seen in the following result. For the statement, let r(D) be the maximum ratio between the length in one dimension and the length in another dimension of a single block.

Theorem 1.1. If r(D) ≤ k, then χ(G(D)) is bounded.

The proof of Theorem 1.1 is presented in Section 2.

Another natural question to ask about block graphs is to obtain bounds on the connectivity. Of course, a general block graph need not be connected or even have any edges so in order to obtain results on connectivity, we must first impose extra restrictions. Since many block graphs arise in applications by partitioning a single block into smaller blocks, we consider the problem of partitioning a d-cube into blocks. A block graph obtained in this manner is trivially connected but Figure 1 shows a partition which yields a block graph with connectivity only 1.

Figure 1. A partition of a cube into blocks with block graph having connectivity 1.

This example can easily be extended to all other values of 2 ≤ d < ∞. In order to avoid a situation like this, a possible solution is to impose an additional restriction that the ratio r(D) is bounded. For any > 0, there exists a configuration like that in Figure 1 with 1 ≤ r(D) ≤ 1+that has connectivity 1. Thus, the only possible case in which a larger connectivity might be achieved is when r = 1.

Theorem 1.2. Let d ≥ 2 and D be the set of blocks resulting from a nontrivial partition of d-cube. If r(D) = 1, then κ(G(D)) ≥ d.

In particular, if d = 2, all blocks are subsquares of a square. Similarly, if d = 3, all blocks are subcubes of a cube. The proof of Theorem 1.2 is presented in Section 3.

2. Proof of Theorem 1.1

Proof. Let \(\mathscr{D}\) be a collection of blocks with \(r(\mathscr{D}) \leq k\), let M be a block of \(\mathscr{D}\) with smallest volume and let m be the vertex of \(G = G(\mathscr{D})\) corresponding to M.

Let \(\ell\) be the length of a longest edge of M and let F be a face of M. Every edge of every other block must have length at least \(\ell/k\). This means that at most \(k^2\) faces of other blocks may fit entirely within F. Also at most k faces of other blocks may touch each edge of F without touching the corners. Finally, we trivially observe that at most 4 other faces may intersect F and contain the corners of F. In total, we get at most \(k^2 + 4k + 4\) possible other blocks touching F. Since there are 6 faces of M, we see that \(d(m) \leq 6(k^2 + 4k + 4)\). (Note that this bound is certainly not the best possible.)

Since there always exists a block of smallest volume, this implies that G is \([6(k^2 + 4k + 4)]\)-degenerate. Using a simple greedy strategy, this gives us the desired bound of \(\chi(G) \le 6(k^2 + 4k + 4) + 1\). This completes the proof of Theorem 1.1.

Note that the bound of \(6(k^2 + 4k + 4) + 1\) on the chromatic number is likely far from the best possible since we make no effort to optimize.

3. Proof of Theorem 1.2

Proof. The proof is by induction on d. Certainly the result holds when d=1 so suppose \(d\geq 2\). Let Q be a d-dimensional cube that is partitioned into (more than one) sub-d-cubes to form a set of blocks \(\mathscr{D}\). Let \(\mathscr{C}\subseteq \mathscr{D}\) be a minimum cut set of blocks. Consider the set of all possible (d-1)-dimensional slices S of Q parallel to a face. Let \(\mathscr{C}'_S\) be the intersection of \(\mathscr{C}\) with S.

If there exists a point \(p \in Q\) that is obstructed by a block of \(\mathscr C\) in each of d different coordinate directions, then \(|\mathscr C| \geq d\) as desired, so suppose not. Then there exists a dimension (say x) such that p is not obstructed by a block of \(\mathscr C\) in either direction (positive or negative). Thus, there must exist at least one such slice S (perpendicular to the x-dimension) that is disconnected by \(\mathscr C'_S\). By induction, there must be at least d-1 blocks in the cut \(\mathscr C'_S\). Let \(p_1\) and \(p_2\) be points in S that are separated by \(\mathscr C'_S\). Let \(p_1\) and \(p_2\) be points in \(p_1\) that is perpendicular to all the dimensions in \(p_1\) and \(p_2\) up to the face of \(p_1\) to form \(p_1^{up}\) and \(p_2^{up}\) and down to the opposite face of \(p_1^{up}\) to form \(p_1^{up}\) and \(p_2^{up}\).

Since \(\mathscr{C}\) is a cut of Q, both of the following must hold.

• Let \(P^{up}\) be a path through Q containing the line from \(p_1\) to \(p_1^{up}\), any path through the top face from \(p_1^{up}\) to \(p_2^{up}\), and finally the line from \(p_2^{up}\) to \(p_2\). Every such path \(P^{up}\) is obstructed by a block of \(\mathscr{C}\).
• Let \(P^{down}\) be a path through Q containing the line from \(p_1\) to \(p_1^{down}\), any path through the bottom face from \(p_1^{down}\) to \(p_2^{down}\), and finally the line from \(p_2^{down}\) to \(p_2\). Every such path \(P^{down}\) is obstructed by a block of \(\mathscr{C}\).

If one of the lines from \(p_i\) to \(p_i^{up}\) or \(p_i^{down}\) is obstructed by a block in \(\mathscr{C}\), then this block is necessarily not a part of \(\mathscr{C}'_S\), meaning that \(|\mathscr{C}| \geq d\), as desired. Thus, we may assume that all paths

through the top face from p up 1 to p up 2 are obstructed and all paths through the bottom face from p down 1 to p down 2 are obstructed. If one of these uses blocks from C 0 S , the other must not, meaning again that |C | ≥ d, as desired.

This completes the proof of Theorem 1.2.

4. Hamiltonicity

Once we have established k-connectivity, one may also ask if the block graphs resulting from partitions of a d-cube are hamiltonian. Unfortunately this is not the case when d = 2 since a simple 3 × 3 grid of squares partitions a square and has a bipartite block graph with 4 vertices in one set and 5 in the other. In order to avoid this trivial example, we may also add edges between vertices whose corresponding blocks have nonempty intersection of any smaller dimension. In particular, when d = 2, this means adding edges between vertices whose blocks share a corner. Let G⁰ (D) denote the block graph with these additional corner edges. Somewhat surprisingly, as seen in the Figure 2, this still does not suffice for hamiltonicity.

Proposition 4.1. There exists a partition D of a square into squares such that G⁰ (D) is not hamiltonian.

Proof. Consider the example pictured in Figure 2.

Figure 2. A non-hamiltonian partition of S into squares.

In this figure, the larger squares form a cut of size 4 producing 5 components so this is clearly not hamiltonian.

Despite this, such graphs may still be hamiltonian for d ≥ 3.

Question. If d ≥ 3 and D be a partition of a d-cube into d-blocks with r(D) = 1, then is G⁰ (D) hamiltonian?

5. Diameter

Another question of practical interest concerns the diameter of block graphs. In general, the diameter could be as small as 2 when G(D) is a star (as in Figure 1) or as large as the number of blocks when G(D) is a path (as in Figure 3).

Figure 3. A partition of a square where G(D) is a path.

Since the structure in Figure 1 can be achieved whenever r(D) > 1, we obtain the following easy result.

Fact 5.1. With r(D) > 1 for a set D of n blocks, we get 2 ≤ diam(G(D)) ≤ n and both bounds are attainable.

Noting that the structure in Figure 1 cannot be achieved when r(D) = 1, the case where r(D) = 1 provides a slightly different lower bound diam(G(D)) ≥ 3 (see Figure 4).

Figure 4. A partition of a square into squares with diam(G(D)) = 3.

On the other end of the spectrum, it seems only natural that the worst case would be when all the blocks are roughly the same size. For this reason, we also consider a notion of a "global ratio" constraint. Let r 0 (D) be the maximum ratio between lengths in any dimension of any blocks. Bounding r 0 (D) provides lower and upper bounds on diam(G(D)).

Theorem 5.1. If r 0 (D) ≤ k, then √d n ^{k ≤} diam(G(D)) ^≤ dk√^{d n}.

Proof. Let \(\mathscr{D}\) be a partition of a unit d-cube Q. Suppose \(G(\mathscr{D})\) has order n and let \(\ell\) be the length of the smallest side of any d-block in \(\mathscr{D}\). Each block has volume at least \(\ell^d\), and consequently \(n < \ell^{-d}\).

Let A and B be blocks of \(\mathscr{D}\) containing opposite corners of Q. To reach B from A along a path in \(G(\mathscr{D})\), every block on this path has side length at most \(k\ell\) in any dimension. Therefore, more than \(\frac{1}{k\ell}\) blocks are needed on such a path, yielding

\[\operatorname{diam}(G(\mathscr{D})) \ge \frac{1}{k\ell} \ge \frac{\sqrt[d]{n}}{k}.\]

Similarly, \(n \geq (k\ell)^{-d}\) as each block is of volume at most \((k\ell)^d\). On any path between any two d-blocks A and B, the distance in any one dimension is less than 1. Since the side length in any one dimension of any block on this path is at least \(\ell\), we use at most \(\frac{1}{\ell}\) blocks in each of the d dimensions. Thus, at most \(d \cdot \frac{1}{\ell}\) blocks are needed in total on this path. Hence

\[\operatorname{diam}(G(\mathscr{D})) \leq \frac{d}{\ell} \leq dk \sqrt[d]{n}.\]

This completes the proof of Theorem 5.1.

Acknowledgement

The work of Hua Wang was partly supported by Simons Foundation (grant #245307) The authors would like to thank Daniel M. Martin for constructive conversations on the topic.

References

• [1] G. Chartrand, L. Lesniak, and P. Zhang. Graphs & digraphs. CRC Press, Boca Raton, FL, fifth edition, (2011).
• [2] C. Magnant and D. M. Martin. Coloring rectangular blocks in 3-space. Discuss. Math. Graph Theory, 31(1) (2011), 161–170.
• [3] B. Reed and D. Allwright. Painting the office. MICS Journal, 1(1) (2008), 1–8.