3 ms·
"More precisely, it is NP-hard1. So it is unlikely that we will find an efficient algorithm to optimally solve the coloring problem on an arbitrary input graph.
by datadrivenangel 2y ago
"More precisely, it is NP-hard1. So it is unlikely that we will find an efficient algorithm to optimally solve the coloring problem on an arbitrary input graph. This fundamental hardness result casts a long shadow across the landscape of graph coloring."
- HarHarVeryFunny 2y agoYes, but in practice heuristic approaches can work well, even if there are no guarantees of optimality. See for example my response about a simple "most constrained first" heuristic.