Editing Graph coloring (section)

=== Computational complexity ===
Graph coloring is computationally hard. It is [[NP-complete]] to decide if a given graph admits a ''k''-coloring for a given ''k'' except for the cases  ''k'' ∈ {{brace|0,1,2}}.  In particular, it is NP-hard to compute the chromatic number.<ref>{{harvtxt|Garey|Johnson|Stockmeyer|1974}};  {{harvtxt|Garey|Johnson|1979}}.</ref> The 3-coloring problem remains NP-complete even on 4-regular [[planar graph]]s.{{sfnp|Dailey|1980}} On graphs with maximal degree 3 or less, however, [[Brooks' theorem]] implies that the 3-coloring problem can be solved in linear time. Further, for every ''k'' > 3, a ''k''-coloring of a planar graph exists by the [[four color theorem]], and it is possible to find such a coloring in polynomial time. However, finding the [[lexicographic order|lexicographically]] smallest 4-coloring of a planar graph is NP-complete.{{sfnp|Khuller|Vazirani|1991}}

The best known [[approximation algorithm]] computes a coloring of size at most within a factor ''O''(''n''(log&nbsp;log&nbsp;''n'')<sup>2</sup>(log&nbsp;n)<sup>−3</sup>) of the chromatic number.{{sfnp|Halldórsson|1993}} For all ''ε''&nbsp;>&nbsp;0, approximating the chromatic number within ''n''<sup>1&minus;''ε''</sup> is [[NP-hard]].{{sfnp|Zuckerman|2007}}

It is also NP-hard to color a 3-colorable graph with 5 colors,{{sfnp|Bulín|Krokhin|Opršal|2019}} 4-colorable graph with 7 colours,{{sfnp|Bulín|Krokhin|Opršal|2019}} and a ''k''-colorable graph with <math>\textstyle\binom k {\lfloor k/2 \rfloor} - 1</math> colors for ''k'' ≥ 5.{{sfnp|Wrochna|Živný|2020}}

Computing the coefficients of the chromatic polynomial is [[Sharp-P-complete|♯P-hard]]. In fact, even computing the value of <math>\chi(G,k)</math> is ♯P-hard at any [[rational point]] ''k'' except for ''k''&nbsp;=&nbsp;1  and ''k''&nbsp;=&nbsp;2.{{sfnp|Jaeger|Vertigan|Welsh|1990}} There is no [[FPRAS]] for evaluating the chromatic polynomial at any rational point ''k''&nbsp;≥&nbsp;1.5 except for ''k''&nbsp;=&nbsp;2 unless [[NP (complexity)|NP]]&nbsp;=&nbsp;[[RP (complexity)|RP]].{{sfnp|Goldberg|Jerrum|2008}}

For edge coloring, the proof of Vizing's result gives an algorithm that uses at most Δ+1 colors. However, deciding between the two candidate values for the edge chromatic number is NP-complete.{{sfnp|Holyer|1981}} In terms of approximation algorithms, Vizing's algorithm shows that the edge chromatic number can be approximated to within 4/3,
and the hardness result shows that no (4/3&nbsp;&minus;&nbsp;''ε'')-algorithm exists for any ''ε&nbsp;>&nbsp;0'' unless [[P&nbsp;=&nbsp;NP]]. These are among the oldest results in the literature of approximation algorithms, even though neither paper makes explicit use of that notion.{{sfnp|Crescenzi|Kann|1998}}