Теорема Візінга

В теорії графів, теорема Візінга (названа на честь Вадіма Візінга, який оприлюднив її в 1964) стверджує, що ребра кожного неорієнтованого графу можна пофарбувати, із використанням числа кольорів не більшого ніж найбільший степінь Δ графу плюс 1.

Завжди необхідно не менше ніж Δ кольорів, отже неорієнтовані графи можна розділити на два класи: «клас один», для якого достатньо Δ кольорів, і «клас два», для якого необхідно Δ + 1.

Приклади

коли Δ = 1, граф G не має двох суміжних ребер і його хроматичне число — один. Тобто всі графи з Δ(G) = 1 належать до першого класу.

Коли Δ = 2, граф G повинен бути диз'юнктним об'єднанням шляхів і циклів. Якщо всі цикли парні, тоді їх можна розфарбувати двома кольорами, чергуючи їх. Якщо ж існує хоч один непарний цикл, тоді розфарбування 2 кольорами неможливе. Тобто граф з Δ = 2 належить до першого класу тоді і тільки тоді, якщо двочастковий.

Мультиграфи зазвичай не коряться теоремі Візінга. Наприклад, мультиграф утворений подвоєнням кожного ребра у трикутнику має максимальну валентність вершини чотири, але його розфарбування вимагає шість кольорів.

Посилання

• Доведення теореми Візінга на PlanetMath. (англ.)