Анотація: Реброва розфарбування. Завдання на графи з кольоровими ребрами і випливають з них властивості. Завдання про незчеплених трикутниках з одноколірними сторонами.
хроматичний індекс
Граф називається реберно - розфарбовуваним. якщо його ребра можна розфарбувати фарбами таким чином, що ніякі два суміжних ребра не опиняться одного кольору. Якщо граф реберно -раскрашіваем, але не є реберно -раскрашіваемим, то називається хроматичним класом або хроматичним індексом. або реберно-хроматичним числом графа. При цьому використовується запис. На малюнку зображений граф, для якого.
Ясно, що якщо найбільша з ступенів вершин графа дорівнює, то. Наступний результат, відомий як теорема Візінга, дає точні оцінки для хроматичного класу графа. Доказ цієї теореми можна знайти у Оре (Ore O. The four-color problem. Academic Press, New York, 1967).
Теорема 7.1. (Візінга, 1964) Нехай в графі, що не має петель, найбільша з ступенів вершин дорівнює тоді.
Завдання, що складається в з'ясуванні того, які графи мають хроматичний клас, а які, не вирішена. Однак в деяких окремих випадках відповідні результати знаходяться легко. Наприклад, чи 3 в залежності від того, парне або непарне, а, при. Хроматичні класи повних графів і повних дводольних графів обчислюються теж просто.