Teoria dei grafi: colorazioni, decomposizioni, etichettature.

Autore: 
Vietri Andrea
Descrizione: 

I grafi sono strutture combinatorie che intervengono in numerose questioni applicative e teoriche. Un grafo consiste di vertici e di specifiche connessioni (spigoli) tra vertici. La colorazione di un grafo può riguardare in particolare i vertici o gli spigoli. Essa ha un chiaro significato in molti modelli reali di ottimizzazione e, d'altra parte, fornisce numerosi spunti di ricerca nell'ambito della combinatoria pura. Un altro importante campo di ricerca è legato alle possibili decomposizioni di grafi in sottografi. L'utilizzo di strutture algebriche (ad es. interpretando i vertici come classi resto) consente di ottenere risultati interessanti. Un settore più specifico ma ricco di problemi aperti e di costruzioni originali è quello delle etichettature graziose, particolari assegnazioni di numeri naturali ai vertici.

© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma