Förfärgningsförlängning

I grafteorin är förfärgningsförlängning problemet med att utöka en graffärgning av en delmängd av en grafs hörn, med en given uppsättning färger, till en färgning av hela grafen som inte tilldelar samma färg till två angränsande hörn .

Komplexitet

Precoloring extension har det vanliga graffärgningsproblemet som ett specialfall, där den initialt färgade delmängden av hörn är tom; därför är den NP-komplett . Men det är också NP-komplett för vissa andra klasser av grafer där det vanliga graffärgsproblemet är lättare. Till exempel är det NP-komplett på tornets grafer , för vilket det motsvarar problemet med att fylla i en delvis ifylld latinsk ruta .

Problemet kan lösas i polynomtid för grafer av begränsad trädbredd , men exponenten för polynomet beror på trädbredden. Det kan lösas i linjär tid för förfärgningsförlängningsinstanser där både antalet färger och trädbredden är avgränsade.

Relaterade problem

Förfärgningsförlängning kan ses som ett specialfall av listfärgning , problemet med att färglägga en graf där inga hörn har färgats, men varje hörn har en tilldelad lista med tillgängliga färger. För att omvandla ett förfärgningsförlängningsproblem till ett listfärgningsproblem, tilldela varje ofärgat hörn i förfärgningsförlängningsproblemet en lista över de färger som ännu inte har använts av dess initialt färgade grannar, och ta sedan bort de färgade hörnen från grafen.

Sudoku- pussel kan modelleras matematiskt som instanser av förfärgningsförlängningsproblemet på Sudoku-grafer .

externa länkar

• Bibliografi om förfärgningsförlängning , Dániel Marx