2014-02-04
908
Наряду с задачей о раскраске вершин известна задача о раскраске ребер графа, когда цвета назначаются ребрам. Раскраска ребер называется правильной, если любые два ребра, имеющие общую вершину, окрашены в разные цвета. Минимальное число цветов, необходимое для правильной раскраски ребер графа G, называется хроматическим индексом графа и обозначается через 
.
В правильной раскраске ребер множество ребер одного цвета образует паросочетание. Поэтому такую раскраску можно трактовать как разбиение множества ребер графа на паросочетания.
Обозначим через 
максимальную степень вершины в графе. При правильной реберной раскраске все ребра, инцидентные одной вершине, должны иметь разные цвета. Отсюда следует, что для любого графа выполняется неравенство 
. Для некоторых графов имеет место строгое неравенство, например, 
, а 
. Следующая теорема показывает, что может отличаться от не более чем на 1.
Теорема Визинга. Для любого графа G справедливо неравенство 
.
