Editing Graph coloring (section)

=== Exact algorithms ===
[[Brute-force search]] for a ''k''-coloring considers each of the <math>k^n</math> assignments of ''k'' colors to ''n'' vertices and checks for each if it is legal. To compute the chromatic number and the chromatic polynomial, this procedure is used for every <math>k=1,\ldots,n-1</math>, impractical for all but the smallest input graphs.

Using [[dynamic programming]] and a bound on the number of [[maximal independent set]]s, ''k''-colorability can be decided in time and space <math>O(2.4423^n)</math>.{{sfnp|Lawler|1976}} Using the principle of [[inclusion–exclusion]] and [[Frank Yates|Yates]]'s algorithm for the fast zeta transform, ''k''-colorability can be decided in time <math>O(2^n n)</math>{{sfnp|Björklund|Husfeldt|Koivisto|2009|page=550}}{{sfnp|Yates|1937|page=66-67}}{{sfnp|Knuth|1997|loc=Chapter 4.6.4, pp. 501-502}}{{sfnp|Koivisto|2004|pp=45, 96–103}} for any ''k''. Faster algorithms  are  known for 3- and 4-colorability, which can be decided in time <math>O(1.3289^n)</math>{{sfnp|Beigel|Eppstein|2005}} and <math>O(1.7272^n)</math>,{{sfnp|Fomin|Gaspers|Saurabh|2007}} respectively. Exponentially faster algorithms are also known for 5- and 6-colorability, as well as for restricted families of graphs, including sparse graphs.{{sfnp|Zamir|2021}}