1
$\begingroup$

I tried finding real life applications for the Four Color Theorem (except for coloring maps) but couldn't find anything useful and well illustrated. For example I found this:

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: construct a graph in which each class is a vertex, and there is 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.

source: jmite on cs.se.

However, I don't really get how it works! Also if you could give more examples related with graph theory and four color theorem

|cite|improve this question
$\endgroup$
  • $\begingroup$ Frankly, I'm not sure that the four color theorem has any real life applications. $\endgroup$ – Yuval Filmus Dec 13 '16 at 10:14
  • 1
    $\begingroup$ The quoted text comes from this answer. If you're going to quote text, you must attribute the source. $\endgroup$ – David Richerby Dec 13 '16 at 12:22
1
$\begingroup$

Explanation of the graph coloring problem stated above:

So each vertex represents a class. Each edge represents a timing conflict between two classes. Suppose there was a graph with 4 vertices and a single edge between two. This would require only 2 colors, which translates to two time slots. Draw this graph. Write out a few scenarios of class schedules and draw their corresponding graphs to get a better idea. Answer the question on whether or not these graphs are planar. If so, what does that mean w.r.t. the four color theorem?

|cite|improve this answer
$\endgroup$
0
$\begingroup$

Anytime graph coloring is applicable, the four color theorem has an opportunity to shine. All you have to do is limit yourself to the type of graph used in this theorem. This could be a possible argument you could make.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ This is, however, quite an artificial application in most cases. For example, in the schedule problem, why would the corresponding graph be planar? $\endgroup$ – Yuval Filmus Dec 13 '16 at 10:13
  • $\begingroup$ In most cases this is likely not meaningful, like a graph representation of a scheduling problem - although if the poster could find an example of this being the case it would be a nice application of this theorem. This is simply a new avenue to pursue for the original poster $\endgroup$ – Logan Leland Dec 13 '16 at 10:16
  • $\begingroup$ can u please explain the graph coloring problem stated above ? $\endgroup$ – sarah lababidi Dec 13 '16 at 10:29

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