With the stronger assumption that Δ ≥ 9, it is possible to find an optimal edge coloring in linear time (Cole & Kowalik 2008).
Ha az erősebb feltétel is teljesül, miszerint Δ ≥ 9, az optimális élszínezés lineáris időben megtalálható (Cole & Kowalik 2008).