# Could chromatic number be easy to calculate when colouring is hard for some graph class?

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.

• Here is also a somewhat related question; some of the answers might give some ideas: cstheory.stackexchange.com/questions/1848/… Sep 5 '18 at 21:05
• Yeah, part about P_5 free graphs is interesting and useful for me, but it's not exactly what I'm talking about. Sep 5 '18 at 21:25
• 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
Sep 11 '18 at 20:18

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.