між існуванням забарвлення та існуванням розбиття множини вершин на незалежні. Твердження 1.3. Граф G є k-розфарбованим тоді і тільки тоді, коли існує розбиття V не більше ніж на k незалежних множин.9 червня 2021 р
Щоб розфарбувати повний граф із n вершинами, Kn, нам потрібно стільки кольорів, скільки вершин (оскільки коли ми призначаємо колір вершині, ми більше не можемо використовувати цей колір знову). Отже, χ(Kn) ≥ n. Але хроматичне число графа не може бути більшим за кількість вершин, тому χ(Kn) = n .
Розфарбування графа – це a присвоєння кольорів кожній з вершин, щоб не було двох суміжних вершин з однаковим кольором.
K-розфарбування графа G є призначення k кольорів, скажімо, 1,2,…,k, вершинам G так, щоб сусідні вершини отримували різні кольори . Граф G називається k-розфарбованим, якщо існує k-розфарбування G. Визначення k-розмальовки не вимагає використання всіх кольорів.
Графік плоский якщо його можна намалювати без перетину країв. Задача про три будинки і три колодязі має розв’язок на торі, але не має розв’язку на площині. Коли граф або мультиграф можна накреслити на площині без двох сегментів, що перетинаються, він називається плоским.
Розфарбування графа є призначення міток, які називаються кольорами, вершинам графа, щоб жодні дві сусідні вершини не мали одного кольору . Хроматичне число χ(G) графа G є мінімальною кількістю кольорів, для яких можливе таке призначення.