Що таке хроматичний показник дводольного графа?
Дводольні графи з хоча б одним ребром мають хроматичне число 2, оскільки дві частини є незалежними наборами і можуть бути розфарбовані одним кольором. І навпаки, якщо граф може бути двоколірним, то він є дводольним, оскільки всі ребра з’єднують вершини різного кольору.
Мінімально необхідна кількість кольорів для ребер даного графа називається хроматичним показником графа. Наприклад, ребра графіка на ілюстрації можуть бути пофарбовані трьома кольорами, але не можуть бути пофарбовані двома кольорами, тому показаний графік має хроматичний індекс три.
Для дводольного мультиграфа хроматичний показник списку дорівнює хроматичному показнику (що, звичайно, те саме, що максимальний ступінь). Це узагальнює результат Янссена щодо повних дводольних графів Km, n з m ≠ n; у випадку Kn, n відповідає на запитання Дініца.
Необхідно мінімум 2 кольори. Це гарантує, що кінцеві вершини кожного ребра будуть забарвлені різними кольорами. Отже, дводольними є графи 2-кольоровий.
За допомогою правильного розфарбування можна знайти хроматичне число графа. Після призначення кольорів, щоб жодна суміжна вершина не була однаковою та використовувалася найменша кількість кольорів, просто підрахуйте, скільки кольорів було використано, щоб знайти хроматичне число. Є 4 вершини, але тільки 3 кольори.