As Kowalik (2009) showed, it is possible to test whether a graph has a 3-edge-coloring in time O(1.344n), while using only polynomial space.
Όπως έδειξε ο Kowalik (2009), γίνεται να ελέγξουμε πότε ένα γράφημα έχει 3 χρώματα για τις ακμές του σε χρόνο O(1.344n), χρησιμοποιώντας μόνο τον πολυωνυμικό χώρο.