The well-known Four color theorem states that every map which is divided into re
ID: 649382 • Letter: T
Question
The well-known Four color theorem states that every map which is divided into regions, can be colored using 4 colors such that no two adjacent regions have the same color.
In fact, there exists a quadratic algorithm for 4-coloring planar graphs.
Suppose you are given a map (e.g. the world's map) and a list of k constraints, e.g. Greece is colored blue, and Spain, Italy and Uruguay are red.
Can this problem be solved in poly time if k is part of the input?
Can this be solved in poly time if k is fixed (i.e. is the problem fixed parameter tractable with respect to k)?
Explanation / Answer
It is NP-complete. Consider a graph G which is modified by duplicating every vertex, and connecting every duplicate vertex to its original. Then if we constrain all the duplicate vertices to a fixed color, then the thus obtained graph is 4-colorable (with constraints) if and only if the original graph is 3-colorable.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.