Wielomian chromatyczny

Wszystkie nieizomorficzne grafy na 3 wierzchołkach i ich wielomianach chromatycznych, zgodnie z ruchem wskazówek zegara od góry. Niezależny 3-zbiór: k ³ . Krawędź i pojedynczy wierzchołek: k ² ( k – 1) . Trójścieżka: k ( k – 1) ² . Klika 3: k ( k – 1)( k – 2) .

Wielomian chromatyczny jest wielomianem grafowym badanym w algebraicznej teorii grafów , gałęzi matematyki . Oblicza liczbę kolorowań wykresu jako funkcję liczby kolorów i został pierwotnie zdefiniowany przez George'a Davida Birkhoffa w celu zbadania problemu czterech kolorów . Został on uogólniony do wielomianu Tutte'a przez Hasslera Whitneya i WT Tutte'a , łącząc go z modelem fizyki statystycznej Potta .

Historia

George David Birkhoff wprowadził wielomian chromatyczny w 1912 roku, definiując go tylko dla grafów planarnych , próbując udowodnić twierdzenie o czterech kolorach . Jeśli $oznacza$ liczbę odpowiednich kolorowań $\ Displaystyle P ( G,4)>0}$ z k kolorami , pokazując dla wszystkich grafów planarnych G . W ten sposób miał nadzieję zastosować potężne narzędzia analizy i algebry do badania pierwiastków wielomianów w problemie kolorowania kombinatorycznego.

Hassler Whitney uogólnił wielomian Birkhoffa z przypadku planarnego na grafy ogólne w 1932 r. W 1968 r. Ronald C. Read zapytał, które wielomiany są wielomianami chromatycznymi pewnego grafu, pytanie, które pozostaje otwarte, i wprowadził koncepcję grafów równoważnych chromatycznie. Obecnie wielomiany chromatyczne są jednym z głównych obiektów algebraicznej teorii grafów .

Definicja

Wszystkie prawidłowe kolory wierzchołków grafów wierzchołków z 3 wierzchołkami przy użyciu k kolorów dla ${\ Displaystyle k = 0,1,2,3}$ . Wielomian chromatyczny każdego wykresu jest interpolowany przez liczbę odpowiednich kolorów.

Dla wykresu $_$ ) wierzchołków k _ -kolorowań _ $k$ powszechnie $\$ lub sol $_ \pi _ {G}(k)}$ . Istnieje unikalny wielomian $P(G,k)$ który oceniany na dowolnej liczbie całkowitej $P(G,x)$ ≥ ≥ 0 coincides with ; it is called the chromatic polynomial of G.

Na przykład, aby pokolorować wykres ścieżki $-$ 3 wierzchołkach kolorami ${\ displaystyle k-1 } pozostałe kolory dla drugiego wierzchołka, a na koniec dla$ można wybrać dowolny z k kolorów dla pierwszego wierzchołka, dowolny z $kolorów , które różnią$ wierzchołka, dowolny z od wyboru drugiego wierzchołka ${\ Displaystyle P (P_ {3}, k) = k \ cdot (k-1) \ cdot (k-$ 1 $}$ liczba k -kolorowań . Dla zmiennej x (niekoniecznie liczby całkowitej) mamy zatem ${\ Displaystyle P (P_ {3}, x) = x(x-1)^{2}=x^{3}-2x^{2}+x}$ . (Kolory, które różnią się tylko permutacją kolorów lub automorfizmami G , są nadal liczone jako różne).

Skreślenie – skrócenie

Główny artykuł: Formuła usuwania – skracania

Fakt, że liczba k -kolorowań jest wielomianem w k wynika z relacji rekurencyjnej zwanej rekurencją delecja-kontrakcja lub fundamentalnym twierdzeniem o redukcji . Opiera się na skróceniu krawędzi $displaystyle$ dla pary wierzchołków $.$ v $v}$ wykres uzyskuje przez połączenie dwóch wierzchołków i usunięcie wszelkich krawędzi ich. Jeśli $displaystyle$ są $uv$$}$ w $v$ , niech wykres uzyskany przez usunięcie krawędzi . Wtedy liczby k -kolorów tych grafów spełniają:

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

$uv$ jeśli $i$ nie sąsiadują ze sobą w sol $i$ jest wykres z dodaną krawędzią $,$ \

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

$Wynika$ to z obserwacji, że każde $k$ G albo daje różne kolory lub te same kolory W pierwszym przypadku daje to (właściwe) $displaystyle G$ -zabarwienie , podczas gdy w drugim przypadku daje zabarwienie $uv$ . $jednoznacznie$ , $-$ k - G można $_$ k kolorowania lub _ _ ${\ displaystyle v}$ nie sąsiadują ze sobą w G ).

Wielomian chromatyczny można zatem rekurencyjnie zdefiniować jako

${\ Displaystyle P (G, x) = x ^ {n}}$ dla wykresu bez krawędzi na n wierzchołkach i

${\ Displaystyle P (G, x) = P (G-uv, x) -P (G / uv, x)}$ dla wykresu G z krawędzią ${\ Displaystyle uv}$ (dowolny wybór).

Ponieważ liczba k -kolorowań wykresu bezkrawędziowego jest rzeczywiście $wielomian$ przez indukcję liczby krawędzi wynika, że ​​dla wszystkich P ( $Displaystyle P(G,x)}$ pokrywa się z liczbą k -kolorowań w każdym punkcie całkowitym x = k . W szczególności wielomian chromatyczny jest unikalnym wielomianem interpolacyjnym stopnia co najwyżej n przechodzącego przez punkty

${\ Displaystyle \ lewo \ {(0, P (G, 0)), (1, P (G, 1)), \ ldots, (n, P (G, n)) \ prawo \}.}$

Tutte , które inne niezmienniki grafów spełniały takie nawroty, doprowadziła go do odkrycia dwuwymiarowego uogólnienia wielomianu chromatycznego, wielomianu Tutte. ${\ Displaystyle T_ {G} (x, y)}$ .

Przykłady

Wielomiany chromatyczne dla niektórych grafów

trójkąt ${\ Displaystyle K_ {3}}$	${\ Displaystyle x (x-1) (x-2)}$
Kompletny wykres ${\ Displaystyle K_ {n}}$	${\ Displaystyle x (x-1) (x-2) \ cdots (x- (n-1))}$
wykres bez krawędzi ${\ Displaystyle {\ overline {K}} _ {n}}$	${\ displaystyle x ^ {n}}$
wykres ścieżki ${\ displaystyle P_ {n}}$	${\ Displaystyle x (x-1) ^ {n-1}}$
Dowolne drzewo o n wierzchołkach	${\ Displaystyle x (x-1) ^ {n-1}}$
cykl ${\ Displaystyle C_ {n}}$	${\ Displaystyle (x-1) ^ {n} + (-1) ^ {n} (x-1)}$
wykres Petersena	${\ Displaystyle x (x-1) ( x-2)\lewo(x^{7}-12x^{6}+67x^{5}-230x^{4}+529x^{3}-814x^{2}+775x-352\prawo)}$

Nieruchomości

Dla ustalonego G na n wierzchołkach wielomian $monicznym$ jest wielomianem stopnia całkowitymi.

Wielomian chromatyczny zawiera co najmniej tyle samo informacji o możliwości barwienia G , co liczba chromatyczna. Rzeczywiście, liczba chromatyczna jest najmniejszą dodatnią liczbą całkowitą, która nie jest zerem wielomianu chromatycznego,

${\ Displaystyle \ chi (G) = \ min \ {k \ w \ mathbb {N}: P (G, k)> 0 \}.}$

Wielomian oszacowany na ${\ Displaystyle (-1) ^ {| V (G) |}}$ daje ( $P.$$\ Displaystyle P (G, -1$ razy liczba acyklicznych orientacji G.

Pochodna $_$$.$ _ _

Jeśli G ma n wierzchołków i c składowych ${\ Displaystyle G_ {1}, \ ldots, G_ {c}}$ , to

• Współczynniki ${\ Displaystyle x ^ {0}, \ ldots, x ^ {c-1}}$ są zerami.
• Wszystkie współczynniki ${\ Displaystyle x ^ {c}, \ ldots, x ^ {n}}$ są niezerowe i naprzemienne w znakach.
• Współczynnik $jest$ 1 (wielomian ) .
• Współczynnik ${\ displaystyle x ^ {n-1}}$ wynosi ${\ Displaystyle - | E (G) |}$ .

$wykresu$ poprzez indukcję liczby krawędzi prostego G z $krawędziami$ i . Kiedy ${\ displaystyle k = 0}$ , G jest pustym wykresem. Stąd z definicji ${\ Displaystyle P (G, x) = x ^ {n}}$ . Tak więc współczynnik $,$ co oznacza dla pustego wykresu $.$ Kiedy ${\ Displaystyle k = 1}$ , jak w G ma tylko jedną krawędź, ${\ Displaystyle P (G, x) = x ^ {n} -x^{n-1}}$ . Zatem współczynnik ${\ Displaystyle x ^ {n-1}}$ wynosi ${\ Displaystyle -1 = - | E (G) |}$ . Tak więc stwierdzenie obowiązuje dla k = 1. Używając silnej indukcji , załóżmy, że stwierdzenie jest prawdziwe dla ${\ Displaystyle k = 0,1,2, \ ldots, (k-1 )}$ . Niech G ma $_$ . Zgodnie z zasadą skracania i usuwania ,

${\ Displaystyle P (G, x) = P (Ge, x) -P (G / e, x)}$ ,

Niech ${\ Displaystyle P (Ge, x) = x ^ {n} -a_ { n-1}x^{n-1}+a_{n-2}x^{n-2}-\cdots } ,$ i ${\ Displaystyle P (G / e, x) = x ^ {n-1} -b_ {n-2} x ^ {n-2} + b_ { n-3}x^{n-3}-\cdots }$ . $(G, x) = x ^ {n} - (a_ {n-1} + 1 )x^{n-1}+\cdots }$ P . Ponieważ ${\ Displaystyle Ge}$ uzyskuje się z G przez usunięcie tylko jednej krawędzi mi , ${\ Displaystyle a_ {n-1} = k-1}$ , więc ${\ Displaystyle a_ {n-1} + 1 = k}$ i dlatego stwierdzenie jest prawdziwe dla k .

• Współczynnik wynosi ( $Displaystyle (-1) ^ {n-1}}$$\$ więcej acyklicznych orientacji, które mają unikalne ujście, określony, dowolnie wybrany wierzchołek.
• Wartości bezwzględne współczynników każdego wielomianu chromatycznego tworzą ciąg logarytmicznie wklęsły .
• ${\ Displaystyle \ scriptstyle P (G, x) = P (G_ {1}, x) P(G_{2},x)\cdots P(G_{c},x)}$

$jest$ przez fakt, że jeśli $G$ jest k -kliką -sumą i ( tj. dwóch w kliki na k wierzchołkach), wtedy

${\ Displaystyle P (G, x) = {\ Frac {P (G_ {1}, x) P (G_ {2}, x)} {x (x-1) \ cdots (xk + 1)} }.}$

Graf G o n wierzchołkach jest drzewem wtedy i tylko wtedy, gdy

${\ Displaystyle P (G, x) = x (x-1) ^ {n-1}.}$

Równoważność chromatyczna

Trzy wykresy z wielomianem chromatycznym równym ${\ Displaystyle (x-2) (x-1) ^ {3} x}$ .

Mówimy, że dwa grafy są chromatycznie równoważne , jeśli mają ten sam wielomian chromatyczny. Grafy izomorficzne mają ten sam wielomian chromatyczny, ale grafy nieizomorficzne mogą być równoważne chromatycznie. Na przykład wszystkie drzewa na n wierzchołkach mają ten sam wielomian chromatyczny. W szczególności ${\ Displaystyle (x-1) ^ {3} x}$ jest wielomianem chromatycznym zarówno wykresu pazurów , jak i wykresu ścieżki na 4 wierzchołkach.

Wykres jest chromatycznie unikalny , jeśli jest określony przez jego wielomian chromatyczny, aż do izomorfizmu. Innymi $G$ G chromatycznie , _ _ _ _ Wszystkie wykresy cykli są chromatycznie unikalne.

Korzenie chromatyczne

Pierwiastek (lub zero ) wielomianu chromatycznego, zwany „pierwiastkiem chromatycznym”, jest wartością x gdzie ${\ Displaystyle P (G, x) = 0$ } . Pierwiastki chromatyczne zostały bardzo dobrze zbadane, w rzeczywistości pierwotną motywacją Birkhoffa do zdefiniowania wielomianu chromatycznego było wykazanie, że dla grafów planarnych ${\ Displaystyle P (G, x)> 0}$ dla x ≥ 4 To ustanowiłoby twierdzenie o czterech kolorach .

Żaden wykres nie może mieć koloru 0, więc 0 jest zawsze pierwiastkiem chromatycznym. Tylko grafy bez krawędzi mogą być jednokolorowe, więc 1 jest pierwiastkiem chromatycznym każdego grafu z co najmniej jedną krawędzią. Z drugiej strony, z wyjątkiem tych dwóch punktów, żaden graf nie może mieć pierwiastka chromatycznego przy liczbie rzeczywistej mniejszej lub równej 32/27. Wynik Tutte łączy ${n}}$$\$ { \ $displaystyle$ phi $}$ jest zatem płaską triangulacją kuli

${\ Displaystyle P (G_ {n}, \ fi ^ {2}) \ równoważnik \ fi ^ {5-n}.}$

Chociaż linia rzeczywista ma zatem duże części, które nie zawierają pierwiastków chromatycznych żadnego wykresu, każdy punkt na płaszczyźnie zespolonej jest arbitralnie blisko pierwiastka chromatycznego w tym sensie, że istnieje nieskończona rodzina grafów, których pierwiastki chromatyczne są gęste na płaszczyźnie zespolonej .

Kolorowanki z wykorzystaniem wszystkich kolorów

Dla wykresu G na n wierzchołkach niech $;$ liczbę kolorowań przy użyciu dokładnie k kolorów do zmiany nazw kolorów (tak więc kolory, można uzyskać od siebie przez permutację kolorów, są liczone jako jeden zabarwienia uzyskane przez automorfizmy G są nadal liczone osobno). Innymi słowy, ${\ Displaystyle e_ {k}}$ zlicza liczbę podziałów zbioru wierzchołków na k (niepustych) niezależnych zestawów . wtedy ${\ Displaystyle k! \ cdot e_ {k}}$ zlicza liczbę kolorowań przy użyciu dokładnie k kolorów (z rozróżnialnymi kolorami). Dla liczby całkowitej x , wszystkie kolory x G można jednoznacznie uzyskać, wybierając liczbę całkowitą k ≤ x , wybierając k kolorów do użycia spośród x dostępnych i kolorowanie przy użyciu dokładnie tych k (rozróżnialnych) kolorów. Dlatego:

${\ Displaystyle P (G, x) = \ suma _ {k = 0} ^ {x} {\ binom {x} {k}} k! \ cdot e_{k}=\suma _{k=0}^{x}(x)_{k}\cdot e_{k}}$ ,

gdzie ${\ Displaystyle (x) _ {k} = x (x-1) (x-2) \ cdots ( x-k+1)}$ oznacza silnię opadającą . Zatem liczby ${\ Displaystyle 1, (x) _ {1}, (x) _ {2}, (x) _ {3}, \ ldots}$ współczynnikami wielomianu w podstawie $\ Displaystyle P ($$( sol , x )$ opadających silni.

Niech za ${\ Displaystyle a_ {k}}$ będzie k -tym współczynnikiem w standardowej podstawie $} \displaystyle 1,x,x^{2},x^{3},\ldots }$$P. ( sol , x ) {\ Displaystyle$ , czyli:

${\ Displaystyle P (G, x) = \ suma _ {k = 0} ^ {n} a_ {k} x ^ {k}}$

Liczby Stirlinga dają zmianę bazy między bazą standardową a bazą opadających silni. Oznacza to:

${\ Displaystyle a_ {k} = \ suma _ {j = 0} ^ {n} (-1) ^ {jk} {\ rozpocząć {bmatrix} j \\ k \ koniec {bmatrix}} e_ {j}}$ i ${\ Displaystyle e_ {k} = \ suma _ {j = 0} ^ {n}{\begin{Bmatrix}j\\k\end{Bmatrix}}a_{j}}$ .

Kategoryzacja

Wielomian chromatyczny jest klasyfikowany przez teorię homologii blisko spokrewnioną z homologią Khovanova .

Algorytmy

Wielomian chromatyczny
Wejście	Graf G z n wierzchołkami.
Wyjście	współczynniki ${\ Displaystyle P (G, x)}$
Czas działania	${\ Displaystyle O (2 ^ {n} n ^ {r})}$ dla pewnej stałej ${\ displaystyle r}$
Złożoność	#P -twarde
Redukcja od	#3SOB

#k-kolorowanki
Wejście	Graf G z n wierzchołkami.
Wyjście	${\ Displaystyle P (G, k)}$
Czas działania	w P. ${\ Displaystyle k = 0,1,2$ , . ${\ Displaystyle O (1,6262 ^ {n})}$ dla ${\ Displaystyle k = 3}$ . W przeciwnym razie ${\ Displaystyle O (2 ^ {n} n ^ {r})}$ dla pewnej stałej ${\ displaystyle r}$
Złożoność	# P -twarde, chyba że ${\ Displaystyle k = 0,1,2}$
Zbliżalność	Brak FPRAS dla ${\ displaystyle k> 2}$

Problemy obliczeniowe związane z wielomianem chromatycznym obejmują

• znalezienie wielomianu chromatycznego danego wykresu G ; ${\ Displaystyle P (G, x)$ }
• oceniając $przy$ _ _ _ _ _

$moglibyśmy$ ponieważ gdybyśmy znali współczynniki, to ocenić w dowolnym momencie czasu n . Trudność drugiego rodzaju problemu silnie zależy od wartości x i była intensywnie badana pod kątem złożoności obliczeniowej . Kiedy x jest liczbą naturalną, ten problem jest zwykle postrzegany jako obliczanie liczby x -kolorów danego wykresu. Na przykład, obejmuje to problem #3-kolorowanie liczenia liczby 3-kolorowań, problem kanoniczny w badaniu złożoności liczenia, kompletny dla klasy liczenia #P .

Wydajne algorytmy

Dla niektórych podstawowych klas grafów znane są wzory zamknięte na wielomian chromatyczny. Na przykład dotyczy to drzew i klik, jak pokazano w powyższej tabeli.

Algorytmy czasu wielomianowego są znane z obliczania wielomianu chromatycznego dla szerszych klas grafów, w tym grafów akordowych i grafów o ograniczonej szerokości kliki . Ta ostatnia klasa obejmuje kografy i grafy o ograniczonej szerokości drzewa , takie jak grafy płaszczyzny zewnętrznej .

Skreślenie – skrócenie

Powtarzalność usuwania i skracania daje sposób obliczania wielomianu chromatycznego, zwanego algorytmem usuwania i skracania . W pierwszej postaci (z minusem) rekurencja kończy się zbiorem pustych grafów. W drugiej formie (z plusem) kończy się zbiorem pełnych wykresów. Stanowi to podstawę wielu algorytmów kolorowania wykresów. Funkcja ChromaticPolynomial w pakiecie Combinatorica systemu algebry komputerowej Mathematica używa drugiego nawrotu, jeśli wykres jest gęsty, i pierwszego nawrotu, jeśli wykres jest rzadki. W najgorszym przypadku czas działania którejkolwiek formuły spełnia tę samą relację powtarzalności, co liczby Fibonacciego , więc w najgorszym przypadku algorytm działa w czasie z wielomianem równym

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

na grafie o n wierzchołkach i m krawędziach. $grafu$ do współczynnika wielomianu rozpinających wejściowego W praktyce strategie rozgałęzień i ograniczeń oraz odrzucanie izomorfizmu grafów są stosowane w celu uniknięcia niektórych wywołań rekurencyjnych, czas działania zależy od heurystyki użytej do wybrania pary wierzchołków.

Metoda kostki

Istnieje naturalna perspektywa geometryczna dotycząca kolorowania grafów, obserwując, że jako przypisanie liczb naturalnych do każdego wierzchołka, kolorowanie grafu jest wektorem w siatce liczb całkowitych. Ponieważ dwa wierzchołki, którym nadano ten sam kolor, są równoważne tym, że $współrzędne$$w$ wektorze kolorowania są równe, $\ displaystyle i}$ 'th i $displaystyle j}$ każda krawędź może być powiązana z hiperpłaszczyzną postaci ${\ Displaystyle \ {x \ w R ^ {d}: x_ {i} = x_ {j} \}}$ . Zbiór takich hiperpłaszczyzn dla danego grafu nazywamy jego układem graficznym . Właściwymi kolorami grafu są te punkty sieci, które unikają zabronionych hiperpłaszczyzn. $zawarte$ zestawu $są$ w sześcianie $-sześcianie , które unikają$ liczbę punktów kratowych w graficznego.

Złożoność obliczeniowa

Problem obliczania liczby 3-kolorowań danego wykresu jest kanonicznym przykładem problemu #P -zupełnego, więc problem obliczania współczynników wielomianu chromatycznego jest #P-trudny. $,$ ocena danego # P Z drugiej strony, dla $(G, k)}$${$ obliczyć, odpowiednie problemy to obliczalny w czasie wielomianowym. Dla liczb $.$$problem$ trudny podobnie jak w przypadku W rzeczywistości wiadomo, że jest # P-trudne dla wszystkich x (w tym ujemnych liczb całkowitych, $)$ trzech „łatwych punktów Tak więc, z perspektywy #P-twardości, złożoność obliczania wielomianu chromatycznego jest całkowicie zrozumiała.

W rozszerzeniu

${\ Displaystyle P (G, x) = a_ {1} x + a_ {2} x ^ {2} + \ cdots +a_{n}x^{n},}$

współczynnik $1$ i znanych jest kilka innych właściwości współczynników. Rodzi to pytanie, czy niektóre współczynniki są łatwe do obliczenia. Jednak problem obliczeniowy obliczenia a _r dla ustalonego r ≥ 1 i danego grafu G jest #P-trudny, nawet dla dwudzielnych grafów planarnych.

Żadne algorytmy aproksymacji do obliczania $x$ są dla żadnego łatwych punktów W punktach całkowitych odpowiedni problem decyzyjny decydujący $czy$ dany wykres może być kolorowy , trudny Takich problemów nie można przybliżyć do żadnego czynnika multiplikatywnego za pomocą algorytmu probabilistycznego z ograniczonym błędem, chyba że NP = RP, ponieważ każde przybliżenie multiplikatywne rozróżniłoby wartości 0 i 1, skutecznie rozwiązując wersję decyzyjną w probabilistycznym czasie wielomianowym z ograniczonym błędem. W szczególności, przy tym samym założeniu, wyklucza to możliwość w pełni wielomianowego losowego schematu aproksymacji czasu (FPRAS) . W przypadku innych punktów potrzebne są bardziej skomplikowane argumenty, a pytanie to jest przedmiotem aktywnych badań. Od 2008 roku wiadomo, że nie ma $>$ do obliczania dla dowolnego x 2 obowiązuje NP RP

Notatki

•   Biggs, N. (1993), teoria grafów algebraicznych , Cambridge University Press, ISBN 978-0-521-45897-9
•   Chao, C.-Y.; Whitehead, EG (1978), „O chromatycznej równoważności wykresów”, Theory and Applications of Graphs , Lecture Notes in Mathematics, tom. 642, Springer, s. 121–131, ISBN 978-3-540-08666-6
•   Dong, FM; Koh, KM; Teo, KL (2005), Wielomiany chromatyczne i chromatyczność grafów , World Scientific Publishing Company, ISBN 978-981-256-317-0
•    Ellis-Monaghan, Joanna A .; Merino, Criel (2011), „Graph wielomiany i ich zastosowania I: wielomian Tutte”, w: Dehmer, Matthias (red.), Strukturalna analiza złożonych sieci , arXiv : 0803,3079 , doi : 10,1007/978-0-8176-4789 -6_9 , ISBN 978-0-8176-4789-6 , S2CID 585250
•    Giménez, O.; Hliněný, P.; Noy, M. (2005), „Obliczanie wielomianu Tutte na wykresach ograniczonej szerokości kliki”, Proc. 31. Międzynarodowy praca. Graph-Theoretic Concepts in Computer Science (WG 2005) , Lecture Notes in Computer Science, tom. 3787, Springer-Verlag, s. 59–68, CiteSeerX 10.1.1.353.6385 , doi : 10.1007/11604686_6 , ISBN 978-3-540-31000-6
•   Goldberg, Luizjana ; Jerrum, M. (2008), „Nieprzybliżenie wielomianu Tutte”, Information and Computation , 206 (7): 908, arXiv : cs/0605140 , doi : 10.1016/j.ic.2008.04.003 , S2CID 53304001
•   Helme-Guizon, Laure; Rong, Yongwu (2005), „Kategoryzacja wielomianu chromatycznego”, Topologia algebraiczna i geometryczna , 5 (4): 1365–1388, arXiv : math / 0412264 , doi : 10,2140 / agt.2005.5.1365 , S2CID 1339633
•    Huh, czerwiec (2012), „Liczby Milnora projekcyjnych hiperpowierzchni i chromatyczny wielomian grafów”, Journal of the American Mathematical Society , 25 (3): 907–927, arXiv : 1008,4749 , doi : 10,1090 / S0894-0347-2012 -00731-0 , MR 2904577 , S2CID 13523955
•   Jackson, B. (1993), „A Zero-Free Interval for Chromatic wielomianów grafów” , kombinatoryka, prawdopodobieństwo i informatyka , 2 (3): 325–336, doi : 10,1017 / S0963548300000705 , S2CID 39978844
•   Jaeger, F.; Vertigan, DL; Welsh, DJA (1990), „O złożoności obliczeniowej wielomianów Jonesa i Tutte”, Mathematical Proceedings of the Cambridge Philosophical Society , 108 (1): 35–53, Bibcode : 1990MPCPS.108...35J , doi : 10,1017 /S0305004100068936 , S2CID 121454726
• Linial, N. (1986), „Trudne problemy z wyliczaniem w geometrii i kombinatoryce”, SIAM J. Algebr. Metody dyskretne , 7 (2): 331–335, doi : 10.1137/0607036
•    Makowski, JA; Rotics, U.; Averbouch, I.; Godlin, B. (2006), „Obliczanie wielomianów grafowych na wykresach ograniczonej szerokości kliki”, Proc. 32. Int. praca. Graph-Theoretic Concepts in Computer Science (WG 2006) , Lecture Notes in Computer Science, tom. 4271, Springer-Verlag, s. 191–204, CiteSeerX 10.1.1.76.2320 , doi : 10.1007/11917496_18 , ISBN 978-3-540-48381-6
•    Naor, J.; Naor, M.; Schaffer, A. (1987), „Szybkie algorytmy równoległe dla wykresów akordowych”, Proc. 19 Symp. ACM. Theory of Computing (STOC '87) , s. 355–364, doi : 10.1145/28395.28433 , ISBN 978-0897912211 , S2CID 12132229 .
•   Oxley, JG; Welsh, DJA (2002), „Wielomiany chromatyczne, przepływowe i niezawodnościowe: złożoność ich współczynników”. , Kombinatoryka, prawdopodobieństwo i informatyka , 11 (4): 403–426, doi : 10,1017 / S0963548302005175 , S2CID 14918970
•   Pemmaraju, S.; Skiena, S. (2003), Computational Discrete Mathematics: Combinatoryics and Graph Theory with Mathematica , Cambridge University Press, sekcja 7.4.2, ISBN 978-0-521-80686-2
• Przeczytaj, RC (1968), „Wprowadzenie do wielomianów chromatycznych” (PDF) , Journal of Combinatorial Theory , 4 : 52–71, doi : 10.1016 / S0021-9800 (68) 80087-0
• Sekine, Kyoko; Imai, Hiroshi; Tani, Seiichiro (1995), „Obliczanie wielomianu Tutte na wykresie średniej wielkości”, w: Staples, John; Eades, Piotr; Katoh, Naoki; Moffat, Alistair (red.), Algorytmy i obliczenia, 6. Międzynarodowe Sympozjum, ISAAC '95, Cairns, Australia, 4–6 grudnia 1995, Proceedings , Lecture Notes in Computer Science, tom. 1004, Springer, s. 224–233, doi : 10.1007/BFb0015427
•   Sokal, AD (2004), „Korzenie chromatyczne są gęste w całej płaszczyźnie zespolonej” , kombinatoryka, prawdopodobieństwo i informatyka , 13 (2): 221–261, arXiv : cond-mat / 0012369 , doi : 10.1017 / S0963548303006023 , S2CID 5549332
• Stanley, RP (1973), „Acykliczne orientacje wykresów” (PDF) , Discrete Math. , 5 (2): 171–178, doi : 10.1016/0012-365X(73)90108-8
•   Wołoszyn, Witalij I. (2002), Kolorowanie mieszanych hipergrafów: teoria, algorytmy i zastosowania. , Amerykańskie Towarzystwo Matematyczne, ISBN 978-0-8218-2812-0
•   Wilf, HS (1986), algorytmy i złożoność , Prentice-Hall, ISBN 978-0-13-021973-2

Linki zewnętrzne

• Weisstein, Eric W. , „Wielomian chromatyczny” , MathWorld
• Wielomian chromatyczny PlanetMath
• Kod do obliczania wielomianów Tutte, Chromatic i Flow autorstwa Gary'ego Haggarda, Davida J. Pearce'a i Gordona Royle'a: [1]