Рёберная раскраска двудольного графа

Основные определения

Определение:

Рёберной раскраской (англ. Edge colouring) графа [math]G(V, E)[/math] называется отображение [math]\varphi:E \rightarrow \{c_{1}...c_{t}\}[/math] — множество красок такое, что для для любых двух различных рёбер [math]e_{i}, e_{j}[/math] инцидентных одной вершине верно, что [math] \varphi (e_{i}) \neq \varphi (e_{j})[/math].

Определение:

Хроматическим индексом (англ. Chromatic index) [math]\chi '(G)[/math] графа [math]G(V, E)[/math] называется такое минимальное число t, что существует рёберная раскраска графа в t цветов.

Некоторое оценки хроматического индекса

Лемма:

[math]\forall\ G(V, E) : \chi '(G) \geq \Delta (G)[/math]

Доказательство:

[math]\triangleright[/math]

Действительно, давайте рассмотрим вершину максимальной степени в графе. Ей инцидентно ровно [math]\Delta(G)[/math] рёбер. При этом, чтобы все они имели попарно различные цвета, они все должны иметь различные цвета, иначе найдётся пара рёбер инцидентных одной вершине имеющих одинаковый цвет.

[math]\triangleleft[/math]

Заметим, что в теории графов доказывается более строгое неравенство, ограничивающее [math]\chi '(G)[/math]. А именно что, [math]\forall\ G(V, E) : \Delta (G) \leq \chi '(G) \leq \Delta (G) + 1[/math]. Однако доказательство этого факта очень громоздко и достойно отдельной статьи.

В данной же статье мы оценим хроматический индекс двудольных графов и предъявим алгоритм их раскраски.