¿Podría ser fácil calcular el número cromático cuando colorear es difícil para alguna clase de gráfico?

Se hizo una pregunta similar antes, pero hubo un error, por lo que no se respondió la clase Graph con un número cromático fácil, pero con coloración NP-hard

¿Hay algún conjunto infinito de gráficos como:$C$

1. Hay un algoritmo polinómico que reconoce para cada gráfico si G pertenece a $G$$G$$C$

2. Existe un algoritmo de tiempo polinómico que calcula el número cromático por cada g ∈ $\chi(g)$$g \in C$

3. La humanidad no conoce un algoritmo de tiempo polinómico para calcular la coloración adecuada para , o (lo que es mejor) hay una prueba de que dicho algoritmo (bajo supuestos razonables) no existe.$C$

Si. Dado que 3-COLORING es FNP-complete, para cualquier problema en FNP podemos construir un gráfico G que sea de 3 colores si y solo si el problema tiene una solución. Por lo tanto, puede elegir su problema favorito de TFNP \ FP (si no está vacío), como encontrar un factor de un número compuesto o un segundo ciclo hamiltoniano en un gráfico de 3 regulares, y convertirlo en un gráfico.

$N$$G(N)$$G(N)$$N$$N$$G(N)$$3$$G(N)$$d$$N$$d$$x_1\ldots x_{n}$$N$$n$$3$$x_i$$d$$3$