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.

7more comments