Cosa significa "Elenco Compiti"?
Indice
L'assegnazione delle liste è un modo per dare delle scelte agli elementi di un grafo. In questo contesto, assegniamo un insieme di valori a ciascun vertice (i punti nel grafo) e a ciascun arco (le linee che collegano i punti).
Per esempio, ogni vertice può avere una lista di numeri, e ogni arco può avere anch'esso la sua lista di numeri. Questa configurazione ci permette di trovare un modo per scegliere numeri da queste liste in modo che vengano soddisfatte certe condizioni, soprattutto quando guardiamo a parti collegate del grafo.
Quando parliamo di come fare questo, ci concentriamo spesso su proprietà specifiche del grafo che aiutano a determinare se è possibile fare queste scelte. Alcuni grafi sono più facili da gestire di altri, soprattutto se seguono certe regole su quanti archi hanno rispetto ai loro vertici.
Numero di Packing delle Liste
Il numero di packing delle liste è un concetto che ci aiuta a capire quante diverse modalità abbiamo per colorare i vertici di un grafo con le liste che abbiamo assegnato. Ogni colore deve provenire dalla lista associata a quel vertice.
L'obiettivo è trovare il numero più piccolo 'k' dove possiamo sempre creare 'k' diversi insiemi di colori che non condividono colori tra di loro. Questa idea è particolarmente interessante quando guardiamo a grafi che non hanno troppi archi collegati a ciascun vertice.
Vogliamo vedere se c'è un limite al numero di colori che possiamo usare in base al numero di archi che collegano ciascun vertice. Questa connessione ci aiuta a vedere le differenze tra il packing delle liste e altri metodi di colorazione usati per i grafi.