Polinomio cromatico

Tutti i grafi non isomorfici su 3 vertici e i loro polinomi cromatici, in senso orario dall'alto. Il 3-insieme indipendente: $k^{3}$. Uno spigolo e un unico vertice: $k^{2}(k-1)$. Il 3-cammino: $k(k-1)^{2}$. La 3-cricca: $k(k-1)(k-2)$.

Il polinomio cromatico è un polinomio studiato nella teoria algebrica dei grafi, una branca della matematica. Esso conta il numero di colorazioni dei grafi come funzione del numero dei colori e fu definito originariamente da George David Birkhoff per affrontare il problema dei quattro colori. Fu generalizzato al polinomio di Tutte da H. Whitney e 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 grafi planari, in un tentativo di dimostrare il teorema dei quattro colori. Se $P(G,k)$ denota il numero di colorazioni esatte di G con k colori, allora si potrebbe enunciare il teorema dei quattro colori mostrando $P(G,4)>0$ 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.

Definizione

Tutte le colorazioni esatte dei vertici dei grafi con 3 vertici usando k colori per $k=0,1,2,3$. 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 colorazioni esatte dei vertici. È denotato comunemente $P_{G}(k)$, $\chi _{G}(k)$, $\pi _{G}(k)$, e $P(G,k)$ che è la notazione che useremo d'ora in avanti.

Per esempio, il grafo lineare $P_{3}$ 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.

Colori disponibili $k$	0	1	2	3
Numero di colorazioni $P(P_{3},k)$	0	0	2	12

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

$\left\{(0,P(G,0)),(1,P(G,1)),\cdots ,(n,P(G,n))\right\}.$

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:

$P(P_{3},t)=t(t-1)^{2},\qquad P(P_{3},3)=12.$

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,

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

Esempi

Polinomi cromatici per certi grafi

Triangolo $K_{3}$	$t(t-1)(t-2)$
Grafo completo $K_{n}$	$t(t-1)(t-2)...(t-(n-1))$
Cammino $P_{n}$	$t(t-1)^{n-1}$
Qualsiasi albero su n vertici	$t(t-1)^{n-1}$
Ciclo $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
Grafo di Petersen	$t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\right)$

Proprietà

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

L'espressione

$(-1)^{|V(G)|}P(G,-1)$

produce il numero di orientazioni acicliche di G.

La derivata stimata a 1, $P'(G,1)$ uguaglia l'invariante cromatica, $\theta (G)$, fino al segno.

Se G ha n vertici, m spigoli e c componenti $G_{1},\cdots ,G_{c}$, allora

• I coefficienti di $t^{0},\cdots ,t^{c-1}$ sono zeri.
• I coefficienti di $t^{c},\cdots ,t^{n}$ sono tutti diversi da zero.
• Il coefficiente di $t^{n}$ in $P(G,t)$ è 1.
• Il coefficiente di $t^{n-1}$ in $P(G,t)$ è $-m$.
• I coefficienti di ogni polinomio cromatico presentano alternanza di segni.
• I valori assoluti dei coefficienti di ogni polinomio cromatico formano una sequenza logaritmicamente concava.
• $\scriptstyle P(G,t)=P(G_{1},t)P(G_{2},t)\cdots P(G_{c},t)$

Un grafo G con n vertici è un albero se e solo se

$P(G,t)=t(t-1)^{n-1}.$

Equivalenza cromatica

I tre grafi con un polinomio cromatico uguale a $(x-2)(x-1)^{3}x$.

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:

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

in particolare,

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

è il polinomio cromatico sia del grafo a stella che del 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 $P(G,t)=P(H,t)$ implicherebbe che G ed H sono isomorfi.

Tutti i grafi ciclo sono cromaticamente unici.

Radici cromatiche

Una radice (o zero) di un polinomio cromatico, chiamata "radice cromatica", è un valore x dove $P(G,x)=0$. 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, $P(G,x)>0$ 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 $\phi$ con lo studio delle radici cromatiche, mostrando che le radici cromatiche esistono molto vicino a $\phi ^{2}$: Se $G_{n}$ è una triangolazione planare di una sfera allora

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

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.

Algoritmi

Polinomio cromatico
Entrata	Grafo G con n vertici.
Uscita	Coefficienti di $P(G,t)$
Tempo di esecuzione	$O(2^{n}n^{r})$ per qualche costante $r$
Complessità	#P-difficile
Riduzione da	#3SAT

#k-colorazioni
Entrata	Grafo G con n vertici.
Uscita	$P(G,k)$
Tempo di esecuzione	In P per $k=0,1,2$. $O(1.6262^{n})$ per $k=3$. Altrimenti $O(2^{n}n^{r})$ per una qualche costante $r$
Complessità	#P-difficile a meno che $k=0,1,2$
Approssimabilità	No FPRAS per $k>2$

I problemi computazionali associati al polinomio cromatico includono

• trovare il polinomio cromatico $P(G,t)$ di un dato grafo G;
• stimare $P(G,k)$ in un punto fisso k per G dato.

Il primo problema è più generale perché se conosciamo i coefficienti di $P(G,t)$ 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 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 #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 grafi cordali e i grafi con un'ampiezza della cricca limitata. Quest'ultima classe comprende i cografi e i grafi con un'ampiezza dell'albero limitata, come i grafi planari esterni.

Cancellazione-contrazione

Un modo di computare il polinomio cromatico si basa sulla contrazione sugli spigoli: per una coppia di vertici $u$ e $v$ il grafo $G/uv$ si ottiene fondendo i due vertici e rimuovendo qualsiasi spigolo tra di essi. Allora il polinomio cromatico soddisfa la relazione di ricorrenza

$P(G,k)=P(G-uv,k)-P(G/uv,k)$

dove $u$ e $v$ sono vertici adiacenti e $G-uv$ è il grafo con lo spigolo $uv$ rimosso. Equivalentemente,

$P(G,k)=P(G+uv,k)+P(G/uv,k)$

se $u$ e $v$ non sono adiacenti e $G+uv$ è il grafo con lo spigolo $uv$ 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. La curiosità di 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. 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

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

su un grafo con n vertici ed m spigoli. L'analisi può essere migliorata entro un fattore polinomiale del numero $t(G)$ degli alberi ricoprenti del grafo in entrata. In pratica, si impiegano le strategie branch and bound e la reiezione dell'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 #P-completo, perciò il problema di computare i coefficienti del polinomio cromatico è #P-difficile. Similmente, stimare $P(G,3)$ per un dato G è #P-completo. D'altro canto, per $k=0,1,2$ è facile computare $P(G,k)$, perciò i problemi corrispondenti sono computabili in tempo polinomiale. Per gli interi $k>3$ il problema è #P-difficile, che è enunciato simile al caso $k=3$. Infatti, è noto che $P(G,x)$ è #P-difficile per tutti gli x (inclusi gli interi negativi e perfino tutti i numeri complessi) eccetto per i tre "punti facili". Così, dalla prospettiva della #P-difficoltà, si comprende completamente la complessità di computare il polinomio cromatico.

Nell'espansione

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

il coefficiente $a_{n}$ è 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_r per un r fisso e un dato grafo G è #P-difficile.

Non si conoscono algoritmi di approssimazione per computare $P(G,x)$ per qualsiasi x eccetto per i tre punti facili. Ai punti interi $k=3,4,\dots$, 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 = 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 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 $P(G,x)$ per qualsiasi x > 2, a meno che non valesse NP = RP.

Bibliografia

• N. Biggs, Algebraic Graph Theory, Cambridge University Press, 1993, ISBN 0-521-45897-8.
• C.-Y. Chao e E. G. Whitehead, On chromatic equivalence of graphs, in Theory and Applications of Graphs, Lecture Notes in Mathematics, vol. 642, Springer, 1978, pp. 121-131, ISBN 978-3-540-08666-6.
• F. M. Dong, K. M. Koh e K. L. Teo, Chromatic polynomials and chromaticity of graphs, World Scientific Publishing Company, 2005, ISBN 981-256-317-2.
• O. Giménez, P. Hliněný e M. Noy, Computing the Tutte polynomial on graphs of bounded clique-width, in Proc. 31st Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2005), Lecture Notes in Computer Science, vol. 3787, Springer-Verlag, 2005, pp. 59-68, DOI:10.1007/11604686_6.
• L.A. Goldberg e M. Jerrum, Inapproximability of the Tutte polynomial, in Information and Computation, vol. 206, n. 7, 2008, p. 908, DOI:10.1016/j.ic.2008.04.003.
• J. Huh, Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs, 2012, arXiv:1008.4749v3.
• F. Jaeger, D. L. Vertigan e D. J. A. Welsh, On the computational complexity of the Jones and Tutte polynomials, in Mathematical Proceedings of the Cambridge Philosophical Society, vol. 108, 1990, pp. 35-53, DOI:10.1017/S0305004100068936.
• N. Linial, Hard enumeration problems in geometry and combinatorics, in SIAM J. Algebraic Discrete Methods, vol. 7, n. 2, 1986, pp. 331-335, DOI:10.1137/0607036.
• J. A. Makowsky, U. Rotics, I. Averbouch e B. Godlin, Computing graph polynomials on graphs of bounded clique-width, in Proc. 32nd Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2006), Lecture Notes in Computer Science, vol. 4271, Springer-Verlag, 2006, pp. 191-204, DOI:10.1007/11917496_18.
• J. Naor, M. Naor e A. Schaffer, Fast parallel algorithms for chordal graphs, in Proc. 19th ACM Symp. Theory of Computing (STOC '87), 1987, pp. 355-364, DOI:10.1145/28395.28433.
• J. G. Oxley e D. J. A. Welsh, Chromatic, flow and reliability polynomials: The complexity of their coefficients., in Combinatorics, Probability, and Computing, vol. 11, n. 4, 2002, pp. 403-426.
• S. Pemmaraju e S. Skiena, sezione 7.4.2, in Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Cambridge University Press, 2003, ISBN 0-521-80686-0.
• K. Sekine, H. Imai e S. Tani, Computing the Tutte polynomial of a graph of moderate size, in Algorithms and Computation, 6th International Symposium, Lecture Notes in Computer Science 1004, Cairns, Australia, Springer, 4–6 dicembre 1995, pp. 224-233.
• A. D. Sokal, Chromatic Roots are Dense in the Whole Complex Plane, in Combinatorics, Probability and Computing, vol. 13, n. 2, 2004, pp. 221-261, DOI:10.1017/S0963548303006023.
• R. P. Stanley, Acyclic orientations of graphs, in Disc. Math., vol. 5, n. 2, 1973, pp. 171-178, DOI:10.1016/0012-365X(73)90108-8.
• Vitaly I. Voloshin, Coloring Mixed Hypergraphs: Theory, Algorithms and Applications., American Mathematical Society, 2002, ISBN 0-8218-2812-6.
• H. S. Wilf, Algorithms and Complexity, Prentice–Hall, 1986, ISBN 0-13-021973-8.

Collegamenti esterni

• (EN) Eric W. Weisstein, Polinomio cromatico, su MathWorld, Wolfram Research.
• (EN) Chromatic polynomial, in PlanetMath.
• (EN) Gary Haggard, David J. Pearce e Gordon Royle,