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

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

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

Рёберной раскраской (англ. 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]\psi '(G)[/math] графа [math]G(V, E)[/math] называется такое минимальное число t, что существует рёберная раскраска графа в t цветов.