Könnte die chromatische Zahl leicht zu berechnen sein, wenn die Färbung für eine Grafikklasse schwierig ist?
Eine ähnliche Frage wurde bereits zuvor gestellt, es gab jedoch einen Fehler, sodass die Graph-Klasse mit einer einfachen chromatischen Zahl, aber einer NP-harten Färbung unbeantwortet blieb Gibt es eine unendliche Menge von Graphen wie:CCC Es gibt einen Polynomalgorithmus, der für jeden Graphen...