Visualizza wikitesto di Polinomio cromatico

[[File:Chromatic polynomial of all 3-vertex graphs BW.png|thumb|Tutti i grafi non isomorfici su 3 vertici e i loro polinomi cromatici, in senso orario dall'alto. Il 3-insieme indipendente: <math>k^3</math>. Uno spigolo e un unico vertice: <math>k^2(k-1)</math>. Il 3-cammino: <math>k(k-1)^2</math>. La 3-cricca: <math>k(k-1)(k-2)</math>.]]

Il '''polinomio cromatico''' è un [[polinomio]] studiato nella [[teoria algebrica dei grafi]], una branca della [[matematica]]. Esso conta il numero di [[Colorazione dei grafi|colorazioni dei grafi]] come funzione del numero dei colori e fu definito originariamente da [[George David Birkhoff]] per affrontare il [[Teorema dei quattro colori|problema dei quattro colori]]. Fu generalizzato al [[polinomio di Tutte]] da [[Hassler Whitney|H. Whitney]] e [[William Thomas Tutte|W. T. Tutte]], legandolo al [[modello di Potts]] della [[fisica statistica]].

==Storia==
[[George David Birkhoff]] introdusse il polinomio cromatico nel 1912, definendolo soltanto per i [[Grafo planare|grafi planari]], in un tentativo di dimostrare il [[teorema dei quattro colori]]. Se <math>P(G, k)</math> denota il numero di colorazioni esatte di ''G'' con ''k'' colori, allora si potrebbe enunciare il teorema dei quattro colori mostrando <math>P(G, 4)>0</math> per tutti i grafi planari ''G''. In questo modo egli sperava di applicare i potenti strumenti dell'analisi e dell'algebra per lo studio delle radici dei polinomi al problema combinatorio delle colorazioni.

[[Hassler Whitney]] generalizzò il polinomio di Birkhoff dal caso planare ai grafi generali nel 1932. Nel 1968 Read chiese che polinomi siano i polinomi cromatici di un determinato grafo, una domanda che rimane aperta, e introdusse il concetto di grafi cromaticamente equivalenti. Oggi, i polinomi cromatici sono uno degli oggetti centrali della [[teoria algebrica dei grafi]].<ref>Vari capitoli {{cita|Biggs (1993)||Biggs1993}}</ref>

==Definizione==
[[File:Chromatic polynomial of all 3-vertex graphs BW with colorings.png|thumb|upright=1.4|Tutte le colorazioni esatte dei vertici dei grafi con 3 vertici usando ''k'' colori per <math>k=0,1,2,3</math>. Il polinomio cromatico di ciascun grafo interpola attraverso il numero di colorazioni esatte.]]

Il polinomio cromatico di un grafo ''G'' conta il numero delle sue [[Colorazione dei vertici|colorazioni esatte dei vertici]]. È denotato comunemente <math>P_G(k)</math>, <math>\chi_G(k)</math>, <math>\pi_G(k)</math>, e <math>P(G, k)</math> che è la notazione che useremo d'ora in avanti.

Per esempio, il [[grafo lineare]] <math>P_3</math> su 3 vertici non può essere colorato affatto con 0 o 1 colori. Con 2 colori, può essere colorato in 2 modi. Con 3 colori, può essere colorato in 12 modi.
{| class="wikitable"
|-
|Colori disponibili <math>k</math> || 0 || 1 || 2 || 3
|-
|Numero di colorazioni <math>P(P_3, k)</math> || 0 || 0 || 2 || 12 
|}

Per un grafo ''G'' con ''n'' vertici, il polinomio cromatico è definito come l'unico [[Interpolazione polinomiale|polinomio interpolante]] di grado al massimo ''n'' attraverso i punti

:<math>\left \{ (0, P(G, 0)), (1, P(G, 1)), \cdots, (n, P(G, n)) \right \}.</math>

Se ''G'' non contiene alcun vertice con un autocappio, allora il polinomio cromatico è un [[polinomio monico]] di grado esattamente ''n''. Infatti per l'esempio di sopra abbiamo:

:<math>P(P_3, t)= t(t-1)^2, \qquad P(P_3, 3)=12.</math>

Il polinomio cromatico include almeno altrettante informazioni sulla colorabilità di ''G'' del numero cromatico. In effetti, il numero cromatico è il più piccolo intero positivo che non sia una radice del polinomio cromatico,
: <math>\chi (G)=\min\{ k : P(G, k) > 0 \}.</math>

==Esempi==
{| class="wikitable" 
|+Polinomi cromatici per certi grafi
|-
| Triangolo <math>K_3</math> || <math>t(t-1)(t-2)</math>
|-
| [[Grafo completo]] <math>K_n</math> || <math>t(t-1)(t-2)...(t-(n-1))</math>
|-
| [[Cammino (teoria dei grafi)|Cammino]] <math>P_n</math> || <math>t(t-1)^{n-1}</math>
|-
| Qualsiasi [[Albero (grafo)|albero]] su ''n'' vertici || <math>t(t-1)^{n-1}</math>
|-
| [[Grafo ciclo|Ciclo]] <math>C_n</math>|| <math>(t-1)^n+(-1)^n(t-1)</math>
|-
| [[Grafo di Petersen]] || <math>t(t-1)(t-2) \left (t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352 \right)</math>
|}

==Proprietà==
Per ''G'' fisso su ''n'' vertici, il polinomio cromatico <math>P(G, t)</math> è in realtà un polinomio di grado ''n''. Per definizione, stimare il polinomio cromatico in <math>P(G, k)</math> produce il numero di ''k''-colorazioni di ''G'' per <math>k=0, 1,\cdots, n</math>. Lo stesso vale per ''k'' > ''n''.

L'espressione
:<math>(-1)^{|V(G)|} P(G,-1)</math> 
produce il numero di [[Grafo aciclico diretto|orientazioni acicliche]] di ''G''.<ref>{{cita|Stanley (1973)||Stanley1973}}</ref>

La derivata stimata a 1, <math>P'(G, 1)</math> uguaglia l'[[invariante cromatica]], <math>\theta(G)</math>, fino al segno.
 
Se ''G'' ha ''n'' vertici, ''m'' spigoli e ''c'' [[Componente connessa (teoria dei grafi)|componenti]] <math>G_1, \cdots, G_c</math>, allora
* I coefficienti di  <math> t^0, \cdots, t^{c-1}</math> sono zeri.
* I coefficienti di <math> t^c, \cdots, t^n</math> sono tutti diversi da zero.
* Il coefficiente di <math>t^n</math> in <math>P(G, t)</math> è 1.
* Il coefficiente di <math>t^{n-1}</math> in <math>P(G, t)</math> è <math>-m</math>.
* I coefficienti di ogni polinomio cromatico presentano alternanza di segni.
* I valori assoluti dei coefficienti di ogni polinomio cromatico formano una [[sequenza logaritmicamente concava]].<ref>{{cita|Huh (2012)||Huh2012}}</ref>
* <math>\scriptstyle P(G, t) = P(G_1, t)P(G_2,t) \cdots P(G_c,t)</math>

Un grafo ''G'' con ''n'' vertici è un albero se e solo se 
:<math>P(G, t) = t(t-1)^{n-1}.</math>

===Equivalenza cromatica===
[[File:Chromatically equivalent graphs.svg|thumb|I tre grafi con un polinomio cromatico uguale a <math>(x-2)(x-1)^3x</math>.]]

Si dice che due grafi sono cromaticamente equivalenti se hanno lo stesso polinomio cromatico. I grafi isomorfi hanno lo stesso polinomio cromatico, ma i grafi non isomorfi possono essere cromaticamente equivalenti. Ad esempio, tutti gli alberi su ''n'' vertici hanno lo stesso polinomio cromatico:

:<math>(x-1)^{n-1}x,</math>

in particolare,

:<math>(x-1)^3x</math>

è il polinomio cromatico sia del [[grafo a stella]] che del [[Cammino (teoria dei grafi)|grafo lineare]] su 4 vertici.

===Unicità cromatica===
Un grafo è cromaticamente unico se è determinato dal suo polinomio cromatico, fino all'isomorfismo. In altre parole, se ''G'' fosse cromaticamente unico, allora <math>P(G, t) = P(H, t)</math> implicherebbe che ''G'' ed ''H'' sono isomorfi.

Tutti i [[Grafo ciclo|grafi ciclo]] sono cromaticamente unici.<ref>{{cita|Chao & Whitehead (1978)||ChaoWhitehead1978}}</ref>

===Radici cromatiche===
Una [[Radice (matematica)|radice]] (o ''zero'') di un polinomio cromatico, chiamata "radice cromatica", è un valore ''x'' dove <math>P(G, x)=0</math>. Le radici cromatidfhe sono state molto ben studiate, infatti, la motivazione originaria di Birkhoff per definire il polinomio cromatico era di mostrare che per i grafi planari, <math>P(G, x)>0</math> per ''x'' ≥ 4. Ciò avrebbe condotto all'enunciazione del [[teorema dei quattro colori]].

Nessun grafo può essere 0-colorato, perciò 0 è sempre una radice cromatica. Solo i grafi senza vertici possono essere 1-colorati, così 1 è la radice cromatica per ogni grafo con almeno uno spigolo. D'altro canto, eccetto per questi due punti, nessun grafo può avere una radice cromatica in un [[numero reale]] minore di o uguale a 32/27. Un risultato di Tutte connette la [[sezione aurea]] <math>\phi</math> con lo studio delle radici cromatiche, mostrando che le radici cromatiche esistono molto vicino a <math>\phi^2</math>:
Se <math>G_n</math> è una triangolazione planare di una sfera allora

:<math>P(G_n,\phi) \leq \phi^{5-n}.</math>

Anche se la linea reale così ha grandi parti che non contengono radici cromatiche per qualsiasi grafo, ogni punto nel [[piano complesso]] è arbitrariamente vicino a una radice cromatica nel senso che esiste una famiglia infinita di grafi le cui radici cromatiche sono dense nel piano planare.<ref>{{cita|Sokal (2004)||Sokal2004}}</ref>

==Algoritmi==
{{infobox
| TitoloInt = Polinomio cromatico
| StileTitoloInt = background: #DD9; font-size: 125%;
| StileNome = font-weight:normal
| Nome1 = Entrata
| Valore1 = Grafo ''G'' con ''n'' vertici.
| Nome2 = Uscita
| Valore2 = Coefficienti di <math>P(G, t)</math>
| Nome3 = Tempo di esecuzione
| Valore3 = <math>O(2^nn^r)</math> per qualche costante <math>r</math>
| Nome4 = Complessità
| Valore4 = [[Sharp-P|#P]]-difficile
| Nome5 = Riduzione da
| Valore5 ={{cancelletto}}3SAT
}}
{{infobox
| TitoloInt = {{cancelletto}}k-colorazioni
| StileTitoloInt = background: #DD9; font-size: 125%;
| StileNome = font-weight:normal
| Nome1 = Entrata
| Valore1 = Grafo ''G'' con ''n'' vertici.
| Nome2 = Uscita
| Valore2 = <math>P(G, k)</math>
| Nome3 = Tempo di esecuzione
| Valore3 = In [[P (complessità)|P]] per <math>k=0,1,2</math>. <math>O(1.6262^n)</math> per <math>k=3</math>. Altrimenti
<math>O(2^nn^r)</math> per una qualche costante <math>r</math>
| Nome4 = Complessità
| Valore4 = [[Sharp-P|#P]]-difficile a meno che <math>k=0,1,2</math>
| Nome5 = Approssimabilità
| Valore5 = No FPRAS per <math>k>2</math>
}}

I [[Problema computazionale|problemi computazionali]] associati al polinomio cromatico includono

* trovare il polinomio cromatico <math>P(G, t)</math> di un dato grafo ''G'';
* stimare <math>P(G, k)</math> in un punto fisso ''k'' per ''G'' dato.

Il primo problema è più generale perché se conosciamo i coefficienti di <math>P(G, t)</math> potremmo stimarlo in qualsiasi punto nel tempo polinomiale perché il grado è ''n''. La difficoltà del secondo tipo di problema dipende fortemente dal valore di ''k'' ed è stato intensamente studiato nella [[Teoria della complessità computazionale|complessità computazionale]]. Quando ''k'' è un [[numero naturale]], questo problema è visto normalmente come computo del numero di ''k''-colorazioni di un dato grafo. Ad esempio, questo comprende il problema '''#3-colorazione''' di contare il numero delle 3-colorazioni, un problema canonico nello studio della complessità del calcolo, completo per la classe di calcolo [[Sharp-P|#P]].

===Algoritmi efficienti===
Per alcune classi di grafi basilari, le formule chiuse per il polinomio cromatico sono conosciute. Ad esempio questo è vero per gli alberi e per le cricche, come elencati nella tabella di sopra.

Gli algoritmi del tempo polinomiale sono noti per il computo del polinomio cromatico per le classi di grafi più ampie, compresi i [[Grafo cordale|grafi cordali]]<ref>{{cita|Naor, Naor & Scahffer (1987)||NaorNaorSchaffer1987}}</ref> e i grafi con un'ampiezza della [[Cricca (teoria dei grafi)|cricca]] limitata.<ref>{{cita|Giménez, Hliněný & Noy (2005)||GiménezHliněnýNoy2005}}; {{cita|Makowsky, Rotics, Averbouch & Godlin (2006)||MakowskyRoticsAverbouchGodlin2006}}</ref> Quest'ultima classe comprende i [[Cografo|cografi]] e i grafi con un'ampiezza dell'[[Albero (grafo)|albero]] limitata, come i [[Grafo planare esterno|grafi planari esterni]].

===Cancellazione-contrazione===
Un modo di computare il polinomio cromatico si basa sulla [[contrazione sugli spigoli]]: per una coppia di vertici <math>u</math> e <math>v</math> il grafo <math>G/uv</math> si ottiene fondendo i due vertici e rimuovendo qualsiasi spigolo tra di essi. Allora il polinomio cromatico soddisfa la relazione di ricorrenza
:<math>P(G,k)=P(G-uv, k)- P(G/uv,k)</math>
dove <math>u</math> e <math>v</math> sono vertici adiacenti e <math>G-uv</math> è il grafo con lo spigolo <math>uv</math> rimosso. Equivalentemente,
:<math>P(G,k)= P(G+uv, k) + P(G/uv,k)</math>
se <math>u</math> e <math>v</math> non sono adiacenti e <math>G+uv</math> è il grafo con lo spigolo <math>uv</math> aggiunto. Nella prima forma, la ricorrenza termina in una collezione di grafi vuoti. Nella seconda forma, essa termina in una collezione di grafi completi. Queste ricorrenze sono chiamate anche  '''Teorema delle riduzioni fondamentali'''.<ref>{{cita|Dong, Koh & Teo||DongKohTeo2005}}</ref> La curiosità di [[William Thomas Tutte|Tutte]] su quali altre proprietà dei grafi soddisfacessero tali ricorrenze lo portarono a scoprire una generalizzazione bivariata del polinomio cromatico, il [[polinomio di Tutte]].

Le espressioni danno origine a una procedura ricorsiva, chiamata ''algoritmo di cancellazione-contrazione'', che forma la base di molti algoritmi per la colorazione dei grafi. La funzione ChromaticPolynomial nel sistema di algebra informatica [[Mathematica]] usa la seconda ricorrenza se il grafo è denso, e la prima ricorrenza se il grafo è sparso.<ref>{{cita|Pemmaraj & Skiena (2003)||PemmarajuSkiena2003}}</ref> Il peggior tempo di esecuzione di entrambe le formule soddisfa la stessa [[relazione di ricorrenza]] della [[successione di Fibonacci]], così, nel caso peggiore, l'algoritmo si svolge nel tempo entro un fattore polinomiale di

:<math>\phi^{n+m}=\left (\frac{1+\sqrt{5}}{2} \right)^{n+m}\in O\left(1.62^{n+m}\right),</math>

su un grafo con ''n'' vertici ed ''m'' spigoli.<ref>{{cita|Wilf (1986)||Wilf1986}}</ref> L'analisi può essere migliorata entro un fattore polinomiale del numero <math>t(G)</math> degli [[Albero ricoprente (matematica)|alberi ricoprenti]] del grafo in entrata.<ref>{{cita|Sekine, Imai & Tani (1995)||SekineImaiTani1995}}</ref> In pratica, si impiegano le strategie ''[[branch and bound]]'' e la reiezione dell'[[Isomorfismo|isomorfismo dei grafi]] per evitare alcune chiamate ricorsive, e il tempo di esecuzione dipende dall'euristica usata per cogliere la coppia di vertici.

===Complessità computazionale===
Il problema di computare il numero di 3-colorazioni di un dato grafo è un esempio canonico di un problema [[Sharp-P|#P]]-completo, perciò il problema di computare i coefficienti del polinomio cromatico è #P-difficile. Similmente, stimare <math>P(G, 3)</math> per un dato ''G'' è #P-completo. D'altro canto, per <math>k=0,1,2</math> è facile computare <math>P(G, k)</math>, perciò i problemi corrispondenti sono computabili in tempo polinomiale. Per gli interi <math>k>3</math> il problema è #P-difficile, che è enunciato simile al caso <math>k=3</math>. Infatti, è noto che <math>P(G, x)</math> è #P-difficile per tutti gli ''x'' (inclusi gli interi negativi e perfino tutti i [[Numero complesso|numeri complessi]]) eccetto per i tre "punti facili".<ref>{{cita|Jaeger, Vertigan & Welsh (1990)||JaegerVertiganWelsh1990}}, basato su una riduzione in {{cita|Linial (1986)||Linial1986}}.</ref> Così, dalla prospettiva della #P-difficoltà, si comprende completamente la complessità di computare il polinomio cromatico.

Nell'espansione

:<math>P(G, t)= a_1 t + a_2t^2+\dots +a_nt^n,</math>

il coefficiente <math>a_n</math> è sempre uguale a 1, e sono note parecchie altre proprietà dei coefficienti. Questo solleva la domanda se alcuni di questi coefficienti siano facili da computare. Tuttavia il problema computazionale di computare ''a<sub>r</sub>'' per un ''r'' fisso e un dato grafo ''G'' è #P-difficile.<ref>{{cita|Oxley & Welsh (2002)||OxleyWelsh2002}}</ref>

Non si conoscono [[Algoritmo di approssimazione|algoritmi di approssimazione]] per computare <math>P(G, x)</math> per qualsiasi ''x'' eccetto per i tre punti facili. Ai punti interi <math>k=3,4,\dots</math>, il corrispondente [[problema di decisione]] di decidere se un dato grafo possa essere ''k''-colorato è [[NP-difficile]]. Tali problemi non possono essere approssimati a qualsiasi fattore moltiplicativo da un [[algoritmo]] probabilistico a errore limitato a meno che NP&nbsp;=&nbsp;RP, perché qualsiasi approssimazione moltiplicativa distinguerebbe i valori 0 e 1, risolvendo efficacemente la versione della decisione nel tempo polinomiale probabilistico con errore limitato. In particolare, in base alla stessa assunzione, questo esclude la possibilità di uno [[schema di approssimazione in tempo polinomiale|schema di approssimazione randomizzato in tempo pienamente polinomiale]] (''fully polynomial time randomised approximation scheme'', FPRAS). Per altri punti, sono necessari argomenti più complicati, e la questione è al centro di ricerche attive. Fino al 2008, non vi era un FPRAS noto per computare <math>P(G, x)</math> per qualsiasi ''x'' > 2, a meno che non valesse [[NP (complessità)|NP]]&nbsp;=&nbsp;[[RP (complessità)|RP]].<ref>{{cita|Goldberg & Jerrum (2008)||GoldbergJerrum2008}}</ref>

==Note==
<references/>

==Bibliografia==
{{Div col|2}}
*{{Cita testo
|cognome=Biggs | nome=N.
|titolo=Algebraic Graph Theory
|editore=Cambridge University Press
|anno=1993
|isbn=0-521-45897-8
|cid=Biggs1993
}}
*{{Cita testo
|cognome1=Chao | nome1=C.-Y.
|cognome2=Whitehead | nome2=E. G.
|contributo=On chromatic equivalence of graphs
|titolo=Theory and Applications of Graphs
|anno=1978
|volume=642
|pp=121-131
|editore=Springer
|serie=Lecture Notes in Mathematics
|isbn=978-3-540-08666-6
|cid=ChaoWhitehead1978
}}
*{{Cita testo
|cognome1= Dong | nome1= F. M.
|cognome2= Koh | nome2= K. M.
|cognome3= Teo | nome3= K. L.
|titolo=Chromatic polynomials and chromaticity of graphs
|editore=World Scientific Publishing Company
|anno=2005
|isbn= 981-256-317-2
|cid=DongKohTeo2005
}}
*{{cita testo
 | cognome1 = Giménez | nome1 = O.
 | cognome2 = Hliněný | nome2 = P.
 | cognome3 = Noy | nome3 = M.
 | contributo = Computing the Tutte polynomial on graphs of bounded clique-width
 | doi = 10.1007/11604686_6
 | pp = 59-68
 | editore = Springer-Verlag
 | serie = Lecture Notes in Computer Science
 | titolo = Proc. 31st Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2005)
 | volume = 3787
 | anno = 2005
 | cid=GiménezHliněnýNoy2005
}}
*{{Cita testo
|cognome1=Goldberg | nome1= L.A.
|cognome2=Jerrum | nome2=  M.
|wkautore2=Mark Jerrum
|titolo= Inapproximability of the Tutte polynomial
|rivista=Information and Computation
|doi= 10.1016/j.ic.2008.04.003
|anno=2008
|volume=206
|p=908
|numero=7
|cid=GoldbergJerrum2008
}}
*{{Cita testo
|cognome=Huh | nome=J.
|titolo=Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs
|anno=2012
|arxiv=1008.4749v3
|cid=Huh2012
}}
*{{Cita testo
|doi= 10.1017/S0305004100068936
|cognome1= Jaeger | nome1= F.
|cognome2= Vertigan | nome2=  D. L.
|cognome3= Welsh | nome3  =D. J. A. 
|titolo= On the computational complexity of the Jones and Tutte polynomials
|rivista=Mathematical Proceedings of the Cambridge Philosophical Society
|volume= 108|pp = 35-53
|anno= 1990
|cid=JaegerVertiganWelsh1990
}}
*{{Cita testo
|doi=10.1137/0607036
|cognome=Linial | nome=N. | wkautore = Nati Linial
|titolo=Hard enumeration problems in geometry and combinatorics
|rivista= SIAM J. Algebraic Discrete Methods
|volume= 7
|numero=2
|pp=331-335
|anno= 1986
|cid=Linial1986
}} 
*{{cita testo
 | cognome1 = Makowsky | nome1 = J. A.
 | cognome2 = Rotics | nome2 = U.
 | cognome3 = Averbouch | nome3 = I.
 | cognome4 = Godlin | nome4 = B.
 | contributo = Computing graph polynomials on graphs of bounded clique-width
 | doi = 10.1007/11917496_18
 | pp = 191-204
 | editore = Springer-Verlag
 | serie = Lecture Notes in Computer Science
 | titolo = Proc. 32nd Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2006)
 | volume = 4271
 | anno = 2006
 | cid=MakowskyRoticsAverbouchGodlin2006
 }}
*{{cita testo
 | cognome1 = Naor | nome1 = J.
 | cognome2 = Naor | nome2 = M.
 | cognome3 = Schaffer | nome3 = A.
 | contributo = Fast parallel algorithms for chordal graphs
 | doi = 10.1145/28395.28433
 | pp = 355-364
 | titolo = Proc. 19th ACM Symp. Theory of Computing (STOC '87)
 | anno = 1987
 | cid=NaorNaorSchaffer1987
}}
*{{Cita testo
|cognome1=Oxley | nome1=J. G.
|cognome2=Welsh | nome2=D. J. A.
|titolo=Chromatic, flow and reliability polynomials: The complexity of their coefficients.
|rivista=Combinatorics, Probability, and Computing
|volume=11
|anno=2002
|numero=4
|pp=403-426
|cid=OxleyWelsh2002
}}
*{{Cita testo
|cognome1=Pemmaraju | nome1=S.
|cognome2=Skiena | nome2=S.
|titolo=Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica
|editore=Cambridge University Press
|anno=2003
|capitolo=sezione 7.4.2
|isbn=0-521-80686-0
|cid=PemmarajuSkiena2003
}}
*{{Cita testo
| cognome1=Sekine | nome1=K.
| cognome2=Imai | nome2=H.
| cognome3=Tani | nome3=S.
| contributo=Computing the Tutte polynomial of a graph of moderate size
| titolo=Algorithms and Computation, 6th International Symposium, Lecture Notes in Computer Science 1004
| città=Cairns, Australia
| editore = Springer
| data=4–6 dicembre 1995
| pp=224-233
| cid=SekineImaiTani1995
}}
*{{Cita testo
|doi=10.1017/S0963548303006023
|cognome=Sokal | nome=A. D. |wkautore=Alan Sokal
|titolo=Chromatic Roots are Dense in the Whole Complex Plane
|rivista=Combinatorics, Probability and Computing 
|anno=2004 
|pp= 221-261
|volume= 13
|numero=2
|cid=Sokal2004
}}
*{{Cita testo
|doi=10.1016/0012-365X(73)90108-8
|cognome=Stanley | nome=R. P.
|titolo=Acyclic orientations of graphs
|rivista=[[Discrete Mathematics|Disc. Math.]] 
|volume=5
|pp=171-178
|anno=1973
|numero=2
|cid=Stanley1973
}}
*{{Cita testo
| cognome=Voloshin | nome=Vitaly I.
| titolo=Coloring Mixed Hypergraphs: Theory, Algorithms and Applications. 
| editore=American Mathematical Society 
| anno=2002
| isbn=0-8218-2812-6
| cid=Voloshin2002
}}
*{{Cita testo
| cognome=Wilf | nome=H. S.
| titolo=Algorithms and Complexity
| editore=Prentice–Hall
| anno=1986
| isbn=0-13-021973-8
| cid=Wilf1986
}}
{{Div col end}}

== Collegamenti esterni ==
* {{Collegamenti esterni}}
* {{PlanetMath|ChromaticPolynomial|Chromatic polynomial}}
* {{en}} Gary Haggard, David J. Pearce e Gordon Royle, {{Collegamento interrotto}}

{{Portale|Matematica}}

[[Categoria:Teoria dei grafi]]