Хроматичен полином
Коментар: Ако добавим ръбове към някаква произволна графика последователно, без да променяме нейните върхове, тогава на някаква стъпка получаваме пълна графика. По същия начин получаваме пълна графика, ако намалим броя на върховете в произволен граф, като ги идентифицираме, без да променяме броя на ръбовете.
Следствие: Хроматичният полином на всяка графика [math] G [/ math] е равен на сумата от хроматичните полиноми на определен брой пълни графики, броят на върховете в които е не повече от графиката [math] G [/ математика] .
Хроматичен полином на пълна графика [редактиране]
[математика] P (K_, x) = x (x-1). (xn + 1) = x ^> [/ math], тъй като първият връх на пълната графика [math] K _ [/ math] може да бъде оцветен във всеки от [math] x [/ math] цветове, а вторият - във всеки от останалите [math] x-1 [/ math] цветове и др. Очевидно е, че ако [math] x [/ math] е по-малко от [math] n [/ math], то полиномът е [math] 0 [/math], тъй като един от факторите му е [math] 0 [/ math] .
Хроматичен полином на нулева графика [редактиране]
[math] P (O_, x) = x ^ [/ math], тъй като всеки от [math] n [/ math] върховете на нулевата графика [math] O _ [/ math] може да бъде независимо оцветен във всеки от [math] x [/ math] цветове.
Забележка: Нулевата графика [math] O _ [/ math] може също да бъде обозначена с [math] \ overline> [/ math] (допълнителна графика за пълната графика [math] K _ [/ math]).
Хроматичен полином на проста верига [редактиране]
Нека [math] T_n [/ math] е проста верига, състояща се от [math] n [/ math] върхове. Помислете за процеса на оцветяване на проста верига: първият връх може да бъде оцветен в един от цветовете [math] x [/ math], вторият и следващите в един от цветовете [math] x - 1 [/ math] ( тоест, така че цветът да не съвпада с предишния пик). Тогава [math] P (T_n, x) = x (x - 1) ^ [/ math] .
Цикъл хроматичен полином [редактиране]
Нека докажем чрез индукция върху броя на върховете.
Индукционна база: разгледаме случая [math] n = 3 [/ math]: [math] P (C_3, x) = x (x - 1) (x - 2) = (x ^ 3 - 3x ^ 2 + 3x - 1) - (x - 1) = (x - 1) ^ 3 + (-1) ^ 3 (x - 1) [/ math], което удовлетворява твърдението на теоремата.
Индукционна връзка: нека [math] P (C_k, x) = (x - 1) ^ k + (-1) ^ k (x - 1) [/ math] .
Да разгледаме случая [math] n = k + 1 [/ math]. По теоремата за рекуррентната формула за хроматични полиноми: [math] P (C_, x) = P (C_ \ setminus e, x) - P (C_/e, x) [/ math] (където [math] e [/math] - всеки ръб [math] C _ [/ math]). Обърнете внимание, че графиката [math] C_/e [/ math] е изоморфна на [math] C_k [/ math], а графиката [math] C_ \ setminus e [/ math] е проста верига.
Хроматичен полином на колелото [редактиране]
Нека [math] W_n [/ math] е колело с [math] n [/ math] върхове. Избирайки и фиксирайки един от [math] x [/ math] цветовете във върха, свързан с всички останали, имаме опции [math] P (C_, x - 1) [/ math] за оцветяване на останалата графика. Тогава хроматичният полином на колелото [math] P_ (x) = x \ cdot P _> (x - 1) = x ((x - 2) ^ - (-1) ^ (x - 2)) [/ math ] .
Хроматичен полином на дърво [редактиране]
[math] \ Rightarrow [/ math]