Matematyka.pl

Podobno istnieje jakiś algorytm, który dany graf trójkolorowalny koloruje używając trzech kolorów tak, że po usunięciu co najwyżej jednego wierzchołka jest to kolorowanie poprawne. Czy ktoś coś o tym wie? Moje poszukiwania nie przyniosły skutku.

Rozumiem, że chodzi o algorytm wielomianowy . Nie wygląda mi to na wiarygodne. W szczególności oznaczałoby to, że każdy graf trójkolorowalny da się w czasie wielomianowym 4-kolorować, a to bym uznał za zadanie bardzo trudne.

edit: rzeczywiście jest to NP-trudne