Guthrie's brother passed on the question to his mathematics teacher Augustus De Morgan at University College, who mentioned it in a letter to William Hamilton in 1852.

The same year, Alfred Kempe published a paper that claimed to establish the result, and for a decade the four color problem was considered solved.

The proof went back to the ideas of Heawood and Kempe and largely disregarded the intervening developments.

Kempe had already drawn attention to the general, non-planar case in 1879,[3] and many results on generalisations of planar graph coloring to surfaces of higher order followed in the early 20th century.

The conjecture remained unresolved for 40 years, until it was established as the celebrated strong perfect graph theorem by Chudnovsky, Robertson, Seymour, and Thomas in 2002.

Since a vertex with a loop (i.e. a connection directly back to itself) could never be properly colored, it is understood that graphs in this context are loopless.

To prove this, both, Mycielski and Zykov, each gave a construction of an inductively defined family of triangle-free graphs but with arbitrarily large chromatic number.

The same class of graphs is used for the construction of a family of triangle-free line segments in the plane, given by Pawlik et al.

Since all edges incident to the same vertex need their own color, we have Moreover, In general, the relationship is even stronger than what Brooks's theorem gives for vertex coloring: A graph has a k-coloring if and only if it has an acyclic orientation for which the longest path has length at most k; this is the Gallai–Hasse–Roy–Vitaver theorem (Nešetřil & Ossona de Mendez 2012).

More generally, the chromatic number and a corresponding coloring of perfect graphs can be computed in polynomial time using semidefinite programming.

If the graph is planar and has low branch-width (or is nonplanar but with a known branch decomposition), then it can be solved in polynomial time using dynamic programming.

Using dynamic programming and a bound on the number of maximal independent sets, k-colorability can be decided in time and space

[15] Using the principle of inclusion–exclusion and Yates's algorithm for the fast zeta transform, k-colorability can be decided in time

The chromatic number satisfies the recurrence relation: due to Zykov (1949), where u and v are non-adjacent vertices, and

[23] In practice, branch and bound strategies and graph isomorphism rejection are employed to avoid some recursive calls.

[24] Another heuristic due to Brélaz establishes the ordering dynamically while the algorithm proceeds, choosing next the vertex adjacent to the largest number of different colors.

Two well-known polynomial-time heuristics for graph colouring are the DSatur and recursive largest first (RLF) algorithms.

The recursive largest first algorithm operates in a different fashion by constructing each color class one at a time.

It does this by identifying a maximal independent set of vertices in the graph using specialised heuristic rules.

In the field of distributed algorithms, graph coloring is closely related to the problem of symmetry breaking.

[27] In a symmetric graph, a deterministic distributed algorithm cannot find a proper vertex coloring.

Richard Cole and Uzi Vishkin[28] show that there is a distributed algorithm that reduces the number of colors from n to O(log n) in one synchronous communication step.

By iterating the same procedure, it is possible to obtain a 3-coloring of an n-cycle in O(log* n) communication steps (assuming that we have unique node identifiers).

Linial (1992) showed that this is not possible: any deterministic distributed algorithm requires Ω(log* n) communication steps to reduce an n-coloring to a 3-coloring in an n-cycle.

The technique by Cole and Vishkin can be applied in arbitrary bounded-degree graphs as well; the running time is poly(Δ) + O(log* n).

[31] The algorithm by Barenboim et al. runs in time O(Δ) + log*(n)/2, which is optimal in terms of n since the constant factor 1/2 cannot be improved due to Linial's lower bound.

This sensing information is sufficient to allow algorithms based on learning automata to find a proper graph coloring with probability one.

[34] On graphs with maximal degree 3 or less, however, Brooks' theorem implies that the 3-coloring problem can be solved in linear time.

The chromatic number of the graph is exactly the minimum makespan, the optimal time to finish all jobs without conflicts.

Ramsey theory is concerned with generalisations of this idea to seek regularity amid disorder, finding general conditions for the existence of monochromatic subgraphs with given structure.