Escuché de un resultado en el color aproximado del gráfico, pero no puedo encontrar la fuente. El resultado es:
Para cada constante existe una suficientemente grande como para que colorear un gráfico coloreable con colores sea NP-duro.
¿Podría alguien señalarme el documento relevante?