Exact coloring of real-life graphs is easy
Olivier Coudert · 1997
Graph coloring has several important applications inVLSI CAD. Since graph coloring is NP-complete, heuristics are used to approximate the optimum solution. But heuristic solutions are typically 10% off, and as much as100% off, the minimum coloring. This paper shows thatsince real-life graphs appear to be 1-perfect, one can indeed solve them exactly for a small overhead.