Similar question was asked before, but there was an error in it so it was left unanswered Graph class with easy chromatic number, but NP-hard coloring

Is there any infinite set of graphs $C$ such as:

  1. There is a polynomial algorithm recognizing for every graph $G$ whether $G$ belongs to $C$

  2. There is a polynomial time algorithm computing chromatic number $\chi(g)$ for every $g \in C$

  3. Humankind does not know a polynomial time algorithm for computing proper colouring for $C$, or (which is better) there is a proof that such an algorithm (under reasonable assumptions) does not exist.

  • $\begingroup$ Here is also a somewhat related question; some of the answers might give some ideas: cstheory.stackexchange.com/questions/1848/… $\endgroup$ – Jukka Suomela Sep 5 '18 at 21:05
  • $\begingroup$ Yeah, part about P_5 free graphs is interesting and useful for me, but it's not exactly what I'm talking about. $\endgroup$ – Janczar Knurek Sep 5 '18 at 21:25
  • $\begingroup$ Maybe a simpler (and weaker) question: Do you know of any result that computes a chromatic number in a purely existential way? That is, the algorithm to computer $\chi(g)$ does not explicitly (or implicitly) generate an actual colouring? I would assume probabilistic existence (existence whp) is not in the scope of this question $\endgroup$ – JimN Sep 11 '18 at 20:18

Yes. Since 3-COLORING is FNP-complete, for any problem in FNP we can construct a graph G that is 3-colorable if and only if the problem has a solution. So you can pick your favorite problem from TFNP\FP (if it's not empty!), like finding a factor of a composite number, or a second Hamiltonian-cycle in a 3-regular graph, and convert it into a graph.

In more detail with the example of finding a factor. We will fix an algorithm that converts a composite number $N$ into a graph $G(N)$ such that from $G(N)$ you can decode the value of $N$. Compositeness of $N$ is a necessary for $G(N)$ to be in our class. Moreover, any proper $3$-coloring of $G(N)$ can be converted into a proper divisor $d$ of $N$. This can be done, e.g., by writing up a CNF that describes whether a given $d$ encoded in binary as $x_1\ldots x_{n}$ divides a fixed $N$ (that also has $n$ digits in binary, but these are not variables). From satisfiability of a CNF there is a standard reduction to 3-COLORABILITY such that you can easily convert a proper $3$-coloring back to an $x_i$ satisfying assignment. Thus solving the coloring problem, you would find a divisor $d$. Moreover, by adding some simple extra gadgets, you can also decide whether a graph is of this form or not. Our class is formed by graphs created this way, which are thus all $3$-colorable.

  • $\begingroup$ To be honest, I don't get your point at all... Could you please say it again, but with a little bit more formalism? I mean, for example I don't see how condition 1. holds in your answer... $\endgroup$ – Janczar Knurek Sep 6 '18 at 17:04
  • $\begingroup$ I've updated my answer. $\endgroup$ – domotorp Sep 6 '18 at 19:08
  • $\begingroup$ The property you are using is, essentially, the FNP-completeness of the search-problem variant of 3-COLORING. This does not follow just from the NP-completeness of 3-COLORING, hence the first sentence is misleading. $\endgroup$ – Emil Jeřábek Sep 6 '18 at 21:18
  • $\begingroup$ Ok, but still, there remains a problem to decide whether a graph is of this form. I understand that there are some standard tools, but I assume you did not check, but you only think they can work? Anyway, thanks, for an answer. $\endgroup$ – Janczar Knurek Sep 6 '18 at 22:52
  • $\begingroup$ @Emil Oops, I thought that it did follow! Thanks for the correction. $\endgroup$ – domotorp Sep 7 '18 at 5:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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