Suatu pewarnaan EDGE yang minimum (minimum edge coloring) pada graph merupakan suatu partisi pada himpunan edge menjadi D matching, konstanta D merupakan derajad vertex terbesar pada graph.Dalam tulisan ini akan dibicarakan dua algoritma pewarnaan edge yang bekerja dalam kompleksitas waktu O (nm), dan O (n^3). Algoritma kedua akan lebih baik (efisien) untuk kasus di mana D merupakan pangkat dari dua.