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 denota il numero di colorazioni esatte di G con k colori, allora si potrebbe enunciare il teorema dei quattro colori mostrando 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.[1]
Definizione
Il polinomio cromatico di un grafo G conta il numero delle sue colorazioni esatte dei vertici. È denotato comunemente , , , e che è la notazione che useremo d'ora in avanti.
Per esempio, il grafo lineare 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
0
1
2
3
Numero di colorazioni
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
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:
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,
Per G fisso su n vertici, il polinomio cromatico è in realtà un polinomio di grado n. Per definizione, stimare il polinomio cromatico in produce il numero di k-colorazioni di G per . Lo stesso vale per k > n.
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:
Un grafo è cromaticamente unico se è determinato dal suo polinomio cromatico, fino all'isomorfismo. In altre parole, se G fosse cromaticamente unico, allora implicherebbe che G ed H sono isomorfi.
Una radice (o zero) di un polinomio cromatico, chiamata "radice cromatica", è un valore x dove . 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, 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 con lo studio delle radici cromatiche, mostrando che le radici cromatiche esistono molto vicino a :
Se è una triangolazione planare di una sfera allora
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.[5]
trovare il polinomio cromatico di un dato grafo G;
stimare in un punto fisso k per G dato.
Il primo problema è più generale perché se conosciamo i coefficienti di 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[6] e i grafi con un'ampiezza della cricca limitata.[7] 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 e il grafo si ottiene fondendo i due vertici e rimuovendo qualsiasi spigolo tra di essi. Allora il polinomio cromatico soddisfa la relazione di ricorrenza
dove e sono vertici adiacenti e è il grafo con lo spigolo rimosso. Equivalentemente,
se e non sono adiacenti e è il grafo con lo spigolo 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.[8] 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.[9] 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
su un grafo con n vertici ed m spigoli.[10] L'analisi può essere migliorata entro un fattore polinomiale del numero degli alberi ricoprenti del grafo in entrata.[11] 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 per un dato G è #P-completo. D'altro canto, per è facile computare , perciò i problemi corrispondenti sono computabili in tempo polinomiale. Per gli interi il problema è #P-difficile, che è enunciato simile al caso . Infatti, è noto che è #P-difficile per tutti gli x (inclusi gli interi negativi e perfino tutti i numeri complessi) eccetto per i tre "punti facili".[12] Così, dalla prospettiva della #P-difficoltà, si comprende completamente la complessità di computare il polinomio cromatico.
Nell'espansione
il coefficiente è 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 ar per un r fisso e un dato grafo G è #P-difficile.[13]
Non si conoscono algoritmi di approssimazione per computare per qualsiasi x eccetto per i tre punti facili. Ai punti interi , 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 per qualsiasi x > 2, a meno che non valesse NP = RP.[14]
N. Biggs, Algebraic Graph Theory, Cambridge University Press, 1993, ISBN0-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, ISBN978-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, ISBN981-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.
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, ISBN0-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.