Хроматичний многочлен

Три графи з хроматичним многочленом, рівним ${\displaystyle (x-2)(x-1)^{3}x}$.

Кажуть, що два графи хроматично еквівалентні, якщо вони мають однакові хроматичні многочлени. Ізоморфні графи мають однакові хроматичні многочлени, але неізоморфні графи можуть бути хроматично еквівалентними. Наприклад, всі дерева з n вершинами мають однакові хроматичні многочлени:

${\displaystyle (x-1)^{n-1}x,}$

Зокрема,

${\displaystyle (x-1)^{3}x}$

є хроматичним многочленом як для клешні, так і для шляху з 4 вершинами.

Граф хроматично унікальний, якщо він визначається хроматичним многочленом з точністю до ізоморфізму. Іншими словами, якщо граф G хроматично унікальний, то з ${\displaystyle P(G,t)=P(H,t)}$ випливає, що G і H ізоморфні.

Всі цикли хроматично унікальні[4].

Корінь (або нуль) хроматичного многочлена (називається «хроматичним коренем») — це значення x, для якого ${\displaystyle P(G,x)=0}$. Хроматичні корені добре вивчено. Фактично, Біркгоф увів хроматичний многочлен, щоб показати, що для планарних графів ${\displaystyle P(G,x)>0}$ для x ≥ 4. Це довело б теорему про чотири фарби.

Ніякий граф не можна розфарбувати в 0 кольорів, так що 0 завжди є хроматичним коренем. Тільки графи без ребер можна розфарбувати в один колір, так що 1 є хроматичним коренем будь-якого графу, що має щонайменше одне ребро. З іншого боку, за винятком цих двох випадків, ніякий граф не може мати хроматичним коренем дійсне число, менше або рівне 32/27[5]. Результат Татта пов'язує золотий перетин ${\displaystyle \phi }$ з вивченням хроматичних коренів, показуючи, що хроматичні корені існують дуже близько до ${\displaystyle \phi ^{2}}$ — якщо ${\displaystyle G_{n}}$ є планарною тріангуляцією сфери, то

${\displaystyle P(G_{n},\phi ^{2})\leq \phi ^{5-n}.}$

Тоді як дійсна пряма, таким чином, має великі шматки, які не містять хроматичних коренів ні для якого графу, будь-яка точка на комплексній площині довільно близька до хроматичного кореня в тому сенсі, що існує нескінченне сімейство графів, хроматичні корені яких щільні на комплексній площині[6].

Хроматичний многочлен категоризовано за допомогою теорії гомологій, близько пов'язаної з гомологією Хованова[7].

Для деяких базових класів графів відомі явні формули хроматичних многочленів. Наприклад, для дерев і клік, що показано в таблиці вище.

Відомі алгоритми поліноміального часу для обчислення хроматичного многочлена для широкого класу графів, до якого входять хордальні графи[8] і графи з обмеженою кліковою шириною[9][10]. Другий з цих класів, своєю чергою, включає кографи і графи з обмеженою деревною шириною, такі як зовніпланарні графи.

В інтернеті робляться спроби розв'язати задачу колективно, і їм допомагають активні автономні помічники, особливо для хроматичних многочленів високого ступеня[11].

Рекурсивний спосіб обчислення хроматичного многочлена базується на стягуванні ребра — для пари вершин ${\displaystyle u}$ і ${\displaystyle v}$ граф ${\displaystyle G/uv}$ виходить шляхом злиття двох вершин і видалення ребра між ними. Хроматичний многочлен задовольняє рекурсивному співвідношенню

${\displaystyle P(G,k)=P(G-uv,k)-P(G/uv,k)}$,

де ${\displaystyle u}$ і ${\displaystyle v}$ є суміжними вершинами і ${\displaystyle G-uv}$ є графом з видаленим ребром ${\displaystyle uv}$. Еквівалентно,

${\displaystyle P(G,k)=P(G+uv,k)+P(G/uv,k)}$

якщо ${\displaystyle u}$ і ${\displaystyle v}$ не суміжні і ${\displaystyle G+uv}$ є графом з доданим ребром ${\displaystyle uv}$. У першій формі рекурсія припиняється на наборі порожніх графів. Ці рекурентні відношення називаються також фундаментальною теоремою редукції[12]. Питання Татта про те, які інші властивості графу відповідають тим самим рекурентним співвідношенням, привело до відкриття узагальнення хроматичного многочлена на дві змінні — многочлена Татта.

Вирази дають рекурсивну процедуру, звану алгоритмом видалення — стягування, яка є основою багатьох алгоритмів розфарбування графів. Функція ChromaticPolynomial у системі комп'ютерної алгебри Mathematica використовує другу рекурентну формулу якщо граф щільний, і першу, якщо граф розріджений[13]. Найгірший час роботи для обох формул задовольняє рекурентному співвідношенням для чисел Фібоначчі, так що в гіршому випадку алгоритм працює за час (з точністю до деякого поліноміального коефіцієнта)

${\displaystyle \phi ^{n+m}=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+m}\in O\left(1{,}62^{n+m}\right)}$

на графі з n вершинами і m ребрами[14]. Аналіз часу роботи можна поліпшити до поліноміального множника числа ${\displaystyle t(G)}$ кістякових дерев вхідного графу[15]. На практиці використовується стратегія гілок і меж разом з відкиданням ізоморфних графів, щоб виключити рекурсивні виклики, і час залежить від евристики, використовуваної при виборі пари вершин (для виключення-стягування).

Існує природний геометричний підхід до розфарбовування графів, якщо зауважити, що при призначенні натуральних чисел кожній вершині розфарбування графів є вектором цілочисельної ґратки. Оскільки присвоєння двом вершинам ${\displaystyle i}$ і ${\displaystyle j}$ одного кольору еквівалентне рівності координат ${\displaystyle i}$ і ${\displaystyle j}$ у векторі розфарбування, кожне ребро можна асоціювати з гіперплощиною виду ${\displaystyle \{x\in R^{d}:x_{i}=x_{j}\}}$. Набір таких гіперплощин для даного графу називається його графічною конфігурацією гіперплощин. Правильне розфарбування графу — це розфарбування, вектор якої не виявляється на забороненій площині. Обмежені множиною кольорів ${\displaystyle k}$, точки решітки потрапляють у куб ${\displaystyle [0,k]^{n}}$. У цьому контексті хроматичний многочлен підраховує точки ґратки в ${\displaystyle [0,k]}$-кубі, які не потрапляють на графічну конфігурацію.

Задача обчислення числа 3-розфарбувань цього графу є канонічним прикладом #P-повної задачі, так що задача обчислення коефіцієнтів хроматичного многочлена #P-складна. Аналогічно, задача обчислення ${\displaystyle P(G,3)}$ для даного графу G #P-повна. З іншого боку, для ${\displaystyle k=0,1,2}$ легко обчислити ${\displaystyle P(G,k)}$, так що відповідні завдання мають поліноміальну за часом складність. Для цілих чисел ${\displaystyle k>3}$ задача #P-складна, що встановлюється подібно до випадку ${\displaystyle k=3}$. Фактично, відомо, що ${\displaystyle P(G,x)}$ #P-складна для всіх x (включно з від'ємними цілими числами і навіть всіма комплексними числами), за винятком трьох «простих точок»[16]. Таким чином, складність обчислення хроматичного многочлена повністю зрозуміла.

У многочлені

${\displaystyle P(G,t)=a_{1}t+a_{2}t^{2}+\dots +a_{n}t^{n},}$

коефіцієнт ${\displaystyle a_{n}}$ завжди дорівнює 1, а також відомі деякі інші властивості коефіцієнтів. Це порушує питання, чи не можна обчислити деякі коефіцієнти простіше. Однак задача обчислення a_r для фіксованого r і даного графу G є #P-складною[17].

Не відомо жодного апроксимаційного алгоритму обчислення ${\displaystyle P(G,x)}$ для будь-якого x, за винятком трьох простих точок. У цілих точках ${\displaystyle k=3,4,\dots }$ відповідна задача розв'язності визначення, чи можна даний граф розфарбувати в k кольорів, NP-складна. Такі задачі не можна апроксимувати з будь-яким коефіцієнтом за допомогою поліноміального ймовірнісного алгоритму з обмеженою помилкою, хіба тільки NP = RP, оскільки будь-яка мультиплікативна апроксимація розрізняла б значення 0 і 1, що було б ефективним розв'язком задачі за допомогою поліноміального ймовірнісного алгоритму з обмеженою помилкою у формі задачі розв'язності. Зокрема, при деяких припущеннях, це виключає можливість повністю поліноміальної рандомізованої апроксимаційної схеми (FPRAS). Для інших точок потрібні складніші міркування і питання перебуває у фокусі активних пошуків. На 2008 рік відомо, що не існує FPRAS-схеми для обчислення ${\displaystyle P(G,x)}$ для будь-якого x > 2, хіба тільки NP = RP[18].