Раскраска

Граф G – ребро К- раскрашиваем, если его ребра можно раскрасить К красками таким образом, что никакие 2 смежных ребра не окажутся одного цвета. Если граф G ребро К – раскрашиваем, но не являются ребро (К-1) раскрашиваем, то К хроматическое число (хроматический класс или хроматический индекс) графа G. Хе(G)=К

3

1 4

2 2 Х(G)=4

3 1 4

 

 

Ясно, что если наибольшая из степеней вершин графа G равна ρ, то Хе(G)≥ρ

Теорема 5:

(Визинг). Пусть в графе G, не имеющем петель, наибольшая из степеней вершин равна ρ, тогда ρ≤Хе(в)≤ρ+1. Пример, известно, что Хе(Сп)=2, если п – четно, Хе(Сп)=3, если нечетно.

Теорема 6:

Хе(Км,п)=ρ=мах( м,п). Хроматический класс любого двудольного графа равен ρ