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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

Посилання