-1
$\begingroup$

We are given a set of squares in the plane with sides parallel to the x-y axes. We know that intersection of every three of them is empty.

Show that we can color these squares with red, blue and green such that each two squares with a intersection receive different colors.

Improve this question
$\endgroup$
1
  • $\begingroup$ I'm not sure but it seems like any such graph would be planar. The result then follows from Grotzsch's theorem. $\endgroup$
    – David Roberson
    Commented Aug 31, 2016 at 15:36

1 Answer 1

Reset to default
1
$\begingroup$

Let $S$ be the set of squares and $E = \{\{s_1, s_2\}: s_1,s_2 \in S \text{ and } s_1 \text{ intersect } s_2\}$.

The graph $(S, E)$ has a planar embedding in the plane where each vertex, $s \in S$, is placed in the center of the square $s$ and each edge, $(s_1, s_2) \in E$ is embedded as a straight line from the vertices $s_1$ to $s_2$. I leave it to the OP to show it is a planar embedding. Hint: show that if an edge in this embedding crosses another edge there is a mutual intersection of at least three squares.

Then as @David E. Roberson stated this follows from Grotzch's Theorem.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .