linguistic:voice_change, information:extraction, linguistic:paraphrasing, stylistic:tone
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 ∈ {0,1,2}. In particular, it is NP-hard to compute the chromatic number. The 3-coloring problem remains NP-complete even on 4-regular planar graphs. 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 lexicographically smallest 4-coloring of a planar graph is NP-complete.

The best known approximation algorithm computes a coloring of size at most within a factor O(n (log log n) (log n)) of the chromatic number. For all ε > 0, approximating the chromatic number within n is NP-hard.

It is also NP-hard to color a 3-colorable graph with 5 colors, 4-colorable graph with 7 colours, and a k -colorable graph with (k ⌊ k / 2 ⌋) − 1 {\displaystyle \textstyle {\binom {k}{\lfloor k/2\rfloor }}-1} colors for k ≥ 5.

Computing the coefficients of the chromatic polynomial is #P-hard. In fact, even computing the value of χ (G, k) {\displaystyle \chi (G,k)} is #P-hard at any rational point k except for k = 1 and k = 2. There is no FPRAS for evaluating the chromatic polynomial at any rational point k ≥ 1.5 except for k = 2 unless NP = RP.

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. 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 − ε)-algorithm exists for any ε > 0 unless P = NP. These are among the oldest results in the literature of approximation algorithms, even though neither paper makes explicit use of that notion.