3.08.7. Реберная раскраска графа

Помимо раскраски вершин рассматриваются также раскраски ребер графов.

Граф G называется реберно K–раскрашиваемым, если его ребра можно раскрасить K красками так, что никакие смежные ребра не будут иметь один и тот же цвет. Наименьшее такое число K называется реберно–хроматическим числом графа G и обозначается χE(G).

Для реберно-хроматического числа справедлива

Теорема (Визниг). Пусть G – мультиграф, максимальная степень вершин которого равна R . Тогда R ≤ χE(G) ≤ r+1 .

< Предыдущая		Следующая >