colorazione dei grafi

Nella teoria dei grafi, la colorazione dei grafi è un caso speciale di ; è un'assegnazione di etichette, tradizionalmente chiamate "colori", agli elementi di un grafo soggetta a determinati vincoli. Nella sua forma più semplice, è un modo di colorare i vertici di un grafo tale che nessuno dei due vertici adiacenti condivida lo stesso colore; questo prende il nome di colorazione dei vertici. Similmente, una colorazione degli spigoli assegna un colore a ogni spigolo in modo che nessuno dei due spigoli adiacenti condivida lo stesso colore, e una colorazione delle facce di un grafo planare assegna un colore a ogni faccia o regione in modo tale che nessuna delle due facce che condividono un confine abbia lo stesso colore. La colorazione dei vertici è il punto di partenza dell'argomento, e gli altri problemi di colorazione possono essere trasformati in una versione dei vertici. Ad esempio, una colorazione degli spigoli di un grafo è solo una colorazione dei vertici del suo , e una colorazione delle facce di un grafo planare è solo una colorazione dei vertici del suo duale. Tuttavia, i problemi di colorazione dei vertici sono spesso dichiarati e studiati come sono. Questo è in parte per la prospettiva, e in parte perché alcuni problemi si studiano meglio in forma diversa dai vertici, com'è ad esempio la colorazione degli spigoli. La convenzione di usare i colori trae origine dalla colorazione dei paesi di una mappa, dove ogni faccia è colorata in senso letterale. Questo fu poi generalizzato alla colorazione delle facce di un grafo nel piano. A causa della dualità planare si passò alla colorazione dei vertici, e in questa forma si generalizza a tutti i grafi. Nelle rappresentazioni matematiche e informatiche, è tipico usare i primi interi positivi o non negativi come "colori". In generale, si può usare qualsiasi insieme finito come "insieme dei colori". La natura del problema della colorazione dipende dal numero dei colori, ma non da quali sono. La colorazione dei grafi gode di molte applicazioni pratiche come pure di molte sfide teoriche. Oltre ai problemi di tipo classico, si possono anche porre diverse limitazioni sul grafo, o sul modo in cui un colore è assegnato, o perfino sul colore stesso. L'argomento ha raggiunto popolarità anche presso il grande pubblico sotto la forma del popolare rompicapo sudoku. La colorazione dei grafi è ancora un campo di ricerca molto attivo. Nota: molti termini usati in questo articolo sono definiti in Glossario di teoria dei grafi.