<p>Even computing a maximum independent set of unit axis-parallel squares is known to be np-hard:</p>
<p><a href="https://www.sciencedirect.com/science/article/pii/0020019081901113?via%3Dihub" rel="nofollow noreferrer">https://www.sciencedirect.com/science/article/pii/0020019081901113?via%3Dihub</a></p>
<p>Since coloring is a &quot;harder&quot; problem, it should also be NP-hard. A constant approximation follows as if a point is covered by <span class="math-container">$k$</span> squares, then the chromatic number is at least <span class="math-container">$k$</span>, and it is not hard to color such a graph using <span class="math-container">$O(k)$</span> colors, observing that the intersection graph has <span class="math-container">$O(nk)$</span> edges.</p>

CC BY-SA 4.0
2021-07-13T16:18:07.290Z
2021-07-14T10:24:40.797Z
2021-07-14T10:24:40.797Z
Sariel Har-Peled
<p>It is known that the coloring intersection graph of axis-parallel rectangles is NP-Hard.
What about squares and more specific case &quot;unit squares&quot;?</p>
<p>Thanks.</p>

<graph-theory><graph-algorithms><np-hardness><graph-colouring><interval-graphs>
Coloring intersection graph of squares
R.hatam
# Coloring intersection graph of squares

(Asked by: username_0 on 2021-07-11)

It is known that the coloring intersection graph of axis-parallel rectangles is NP-Hard.
What about squares and more specific case "unit squares"?

Thanks.

**Tags:** graph-theory, graph-algorithms, np-hardness, graph-colouring, interval-graphs


---

## 1 answers

### Answer by username_1 on 2021-07-13. Score: 4

Even computing a maximum independent set of unit axis-parallel squares is known to be np-hard:

<https://www.sciencedirect.com/science/article/pii/0020019081901113?via%3Dihub>

Since coloring is a "harder" problem, it should also be NP-hard. A constant approximation follows as if a point is covered by $k$ squares, then the chromatic number is at least $k$, and it is not hard to color such a graph using $O(k)$ colors, observing that the intersection graph has $O(nk)$ edges.


---

