<p>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.</p>

<p>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.</p>

CC BY-SA 4.0
2018-09-06T17:04:49.680Z
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...
Janczar Knurek
CC BY-SA 4.0
2018-09-06T19:08:38.670Z
I've updated my answer.
domotorp
CC BY-SA 4.0
2018-09-06T21:18:10.470Z
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.
Emil Jeřábek
CC BY-SA 4.0
2018-09-06T22:52:37.923Z
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.
Janczar Knurek
CC BY-SA 4.0
2018-09-07T05:33:10.597Z
@Emil Oops, I thought that it did follow! Thanks for the correction.
domotorp
CC BY-SA 4.0
2018-09-07T05:35:03.850Z
@Janczar Since there are just polynomially many gadgets/vertices in G(n), we can just mark each by connecting each to some (differently sized) huge clique.
domotorp
CC BY-SA 4.0
2018-09-06T12:34:37.213Z
2018-09-07T05:32:30.340Z
2018-09-07T05:32:30.340Z
domotorp
<p>Similar question was asked before, but there was an error in it so it was left unanswered <a href="https://cstheory.stackexchange.com/questions/33737/graph-class-with-easy-chromatic-number-but-np-hard-coloring">Graph class with easy chromatic number, but NP-hard coloring</a></p>

<p>Is there any infinite set of graphs $C$ such as:</p>

<ol>
<li><p>There is a polynomial algorithm recognizing for every graph $G$ whether $G$ belongs to $C$</p></li>
<li><p>There is a polynomial time algorithm computing chromatic number $\chi(g)$ for every $g \in C$</p></li>
<li><p>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.</p></li>
</ol>

CC BY-SA 4.0
2018-09-05T21:05:29.357Z
Here is also a somewhat related question; some of the answers might give some ideas: https://cstheory.stackexchange.com/questions/1848/easy-decision-problem-hard-search-problem
Jukka Suomela
CC BY-SA 4.0
2018-09-05T21:25:02.430Z
Yeah, part about P_5 free graphs is interesting and useful for me, but it's not exactly what I'm talking about.
Janczar Knurek
CC BY-SA 4.0
2018-09-11T20:18:58.247Z
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
JimN
<graph-theory><graph-algorithms>
Could chromatic number be easy to calculate when colouring is hard for some graph class?
Janczar Knurek
# Could chromatic number be easy to calculate when colouring is hard for some graph class?

(Asked by: username_0 on 2018-09-05)

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](https://cstheory.stackexchange.com/questions/33737/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.

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_1**: Here is also a somewhat related question; some of the answers might give some ideas: https://cstheory.stackexchange.com/questions/1848/easy-decision-problem-hard-search-problem  
> **username_0**: Yeah, part about P_5 free graphs is interesting and useful for me, but it's not exactly what I'm talking about.  
> **username_2**: 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  

---

## 1 answers

### Answer by username_3 on 2018-09-06. Score: 4

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.

> **Comments:**
> **username_0**: 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...  
> **username_3**: I've updated my answer.  
> **username_4**: 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.  
> **username_0**: 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.  
> **username_3**: @Emil Oops, I thought that it did follow! Thanks for the correction.  
> **username_3**: @Janczar Since there are just polynomially many gadgets/vertices in G(n), we can just mark each by connecting each to some (differently sized) huge clique.  

---

