I was reading up on the four color theorem and am wondering if there is any practical application of it. (I dont think seperating the map into four different colors can be considered an application.)

I tried Googling for applications but couldn't find any.

  • Since it had been known that five colors do suffice (with a simple proof), the real question is: what application benefits from the fact that four rather than five colors suffice. – Yuval Filmus Apr 28 '15 at 21:37
  • Arguably colouring maps isn't an application, since the theorem doesn't allow for disconnected territories. For example, Alaska, Hawaii and the continental US all need to be the same colour. The possibility of disconnected territories means that the graph corresponding to a map isn't necessarily planar: indeed any graph with $m$ edges can be realized by having $m$ islands such that countries $i$ and $j$ share an island iff $ij$ is an edge in the graph. I can't remember if the actual world map is 4-colourable; it probably is. – David Richerby May 12 '17 at 20:50

One of the 4 Color Theorem most notable applications is in mobile phone masts. These masts all cover certain areas with some overlap meaning that they can’t all transmit on the same frequency. A simple method of ensuring that no two masts that overlap have the same frequency is to give them all a different frequency. But, as the government owns all frequencies and charge for each, one wants to use the minimum possible number of frequencies. The areas covered can be drawn as a map and the different frequencies can be represented as colors.

  • In other words, assuming that a four coloring can be found efficiently, you only need to reserve four frequencies in advance even if the exact location of the masts is unknown (or even could change). – Yuval Filmus Apr 28 '15 at 19:27
  • 1
    Is this really true? The graph isn't guaranteed to be planar (five masts close enough together will induce a $K_5$ subgraph) so it isn't guaranteed to be four-colourable. – David Richerby Apr 28 '15 at 20:58
  • @YuvalFilmus Planar graphs can be four-coloured in quadratic time: Robertson, Sanders, Seymour and Thomas, "Efficiently four-coloring planar graphs", Proc. STOC 1996 (PDF). – David Richerby Apr 28 '15 at 21:02
  • Actually, allow me to come back and make a stronger statement. This isn't true, precisely because five closely-placed masts result in a $K_5$. In fact, this is an application of the fact that there is a polynomial time algorithm to compute the chromatic number of unit disk graphs, which aren't necessarily planar and aren't necessarily 4-colourable. – David Richerby May 12 '17 at 20:57

Graph coloring problems are widely applicable to the problem of scheduling.

Consider a University, where you are trying to schedule times for all of the final exams. Some students are taking more than one class, so you want to make sure they don't have two exams scheduled at the same time. However, you want your exam writing period to be as short as possible, to run as many exams concurrently as you can.

You can represent this as a Graph coloring problem: you make $G=(V,E)$ where each class is a vertex, and an edge between vertices any time a two classes contain the same student. Your colors will represent different exam timeslots. The minimum number with which you can color that graph is the smallest number of timeslots you need to write all your exams.

The problem in general is NP hard, but if you had some knowledge about your schedule, say, that it was planar, then you could apply the 4-color theorem to write all of the exams together.

I'm not 100% certain you'd ever get a planar graph in a real-life scheduling problem, but there's a wider lesson here: graphs are widely applicable to things which aren't immediately obvious. The 4-color theorem isn't just about graphs and maps, it can be used to model real life problems where you're expressing some set of objects, and some binary relations between those objects.

  • 1
    It seems relatively unlikely that you'd get a planar graph in a scheduling problem since, as you say, that would allow you to solve everything using only four slots. (For example, in the specific example you give, the graph isn't planar if there's a single student taking five classes.) – David Richerby Mar 21 '14 at 22:07

yes planar graph $n$-coloring for low/fixed $n$ has minimal applications, mainly planar map coloring. however $n$-coloring for arbitrary $n$ is NP complete, it was one of the 1st problems proven NP complete, hence tying into the massive edifice of theory. but actually even $n$-coloring can be reduced to 3-coloring via a basic transformation.[1] so $n$ coloring for $n \geq 3$ is NP complete (but not restricted to planar graphs). there are probably other reductions to 4-coloring & planar maps studied in the literature. ie to get a better feel of its significance one would have to study the possible reductions to it which is a complex/advanced/wideranging topic.

but another angle is that the question of 4-coloring of a planar map/graph was a difficult open problem in mathematics/computer science for many decades (actually over 1½ century old, and one of the earliest highly advanced graph problems). mathematics advances through solving unsolved problems. it fits into a common core pattern of "problems that are easy to state but the solutions/proofs were inaccessable for a long time and are very complex". this is a fundamental asymmetry widespread in math that shows the limits of mathematical/theoretical leverage.

the techniques that are found to succeed can be applied to other unsolved problems and sometimes open new theoretical/conceptual vistas/abstractions. sometimes remarkable proofs are valuable in their own right and the 4-Color theorem fits this category. it is one of the most sophisticated early automated theorem proofs. further work has gone into improved human-readable simplifications since it was discovered and caused a relative shock through the theoretical community on its announcement, and sparked much further analysis and commentary. it serves as a key benchmark/milestone/test case for improvements in automated theorem proving.

[1] 3 coloring is NP complete

  • 1
    It's probably a good idea to use a symbol different than $n$ to denote the number of colors, since $n$ often denotes the cardinality of the vertex set. Also, we do not know how to 3-color planar graphs in polynomial time. – Juho May 12 '17 at 18:22

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.