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



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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.