Ограничения на количество цветов в рёберной раскраске графа возникают из-за требования, чтобы никакие два сопряжённых ребра не имели один и тот же цвет. 34

Другими словами, в рёберной раскраске рёбра одного цвета должны быть несмежны, то есть образовывать паросочетание. 12 Если размер максимального паросочетания в заданном графе мал, то для покрытия всех рёбер графа потребуется большое число паросочетаний, а значит, и различных цветов. 12

Минимальное требуемое число цветов для раскраски рёбер заданного графа называется хроматическим индексом графа. 34