This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each child drew a graph as a challenge, to be colored by her partner, using the fewest possible number of colors. In another activity, the children produced maps to be 4-colored by their partners.
My question here concerns the actual computational difficulty of these tasks.
Question. Is it easy to come up with hard-to-color graphs? More precisely:
-
Is there a polynomial-time algorithm (in the desired number of vertices) that produces graphs $\Gamma_n$ with $n$ vertices on input $n$, such that there is no polynomial-time algorithm that computes the chromatic numbers of those graphs?
-
Is there a polynomial-time algorithm producing graphs $\Delta_n$ with $n$ vertices and stating the chromatic number $c_n$ of $\Delta_n$, such that there is no polynomial-time algorithm producing a $c_n$-coloring of $\Delta_n$?
-
Is there a polynomial-time algorithm (in the desired number of countries) that produces maps (planar graphs) of a desired size, such that there is no polynomial-time algorithm that computes 4-colorings of those maps?
Evidently, graph-coloring is hard in general. But is it easy to produce hard instances of a desired size?
If there are affirmative answers, then one could impose further requirements, such as insisting that there is no infinite subsets of the graphs that admit a polynomial-time algorithm computing the chromatic numbers or the colorings. This would be a sense in which nearly every instance is hard.
Best Answer
Since nobody seems to have addressed question 3, I will. The proofs of the 4-colour theorem are effective in the sense that they can be turned into polynomial-time algorithms. So there are no planar graphs for which 4-colouring is hard.