3

Is there a such result for volume in general ? and for space of higher dimension ?

What I mean is for example, if you break a brick in many pieces and you restick them again, how many color at most do you need to color them such that there is no adjacent color ?

Surb
  • 55,662
  • The four color theorem is fundamentally a statement about planar graphs. I am not sure how to even define a graph to be "3D" using only graph theory language. In fact I think even a complete graph might be able to be embedded in 3 dimensions, since line segments do not divide the space. If I'm correct then I don't think your question about bricks is well-modeled by ordinary graphs. – Ian Apr 04 '15 at 19:29
  • @Ian See this old question – bof Apr 04 '15 at 19:46

2 Answers2

4

There is a visual demonstration about the lack of a small constant bound here: http://demonstrations.wolfram.com/AnInfinitelyColorableSetOf3DRegions/

peterm
  • 565
2

You can embed the complete graph on $n$ vertices as the adjacency of regions of 3D space - so you can need arbitrarily many colors to color any given graph. I can't think of a simple explicit formula for such a set of regions of space, but a construction can be seen fairly easily:

Choose $n$ disjoint closed balls in 3-space, representing each vertex. For each pair of balls, choose some closed path beginning in one and ending in the other, such that no two of these paths intersect. We will color each ball, along with any paths beginning in it as one color. (This is possible since we can always perturb the paths in 3-space so as not to intersect). This colors some subset of 3-space. Then, we can color any other point $p$ the same color as the closest colored point to $p$.

These regions will clearly all be adjacent to each other, as each has a tendril reaching out to each other one. It will require $n$ colors to color.

Milo Brandt
  • 60,888