Komplett färgläggning - Complete coloring

Komplett färgläggning av Clebsch-grafen med 8 färger. Varje par färger visas på minst en kant. Det finns ingen fullständig färgning med fler färger: i någon 9-färgning visas en viss färg bara vid en topp, och det skulle inte finnas tillräckligt med närliggande hörn för att täcka alla par som involverar den färgen. Därför är det akromatiska antalet i Clebsch-grafen 8.

I grafteori , komplett färg är motsatsen till en harmonisk färg i den meningen att det är en vertex färg där varje par av färger visas på åtminstone ett par av angränsande hörn. Likaså är en komplett färgning minimal i den meningen att den inte kan omvandlas till en korrekt färgning med färre färger genom att slå samman par färgklasser. Det akromatiska talet ψ (G) i en graf G är det maximala antalet färger som är möjlig i en fullständig färgning av G.

Komplexitetsteori

Att hitta ψ (G) är ett optimeringsproblem . Den beslutsproblem för fullständig färgning kan formuleras som:

INSTANCE: ett diagram och ett positivt heltal${\ displaystyle G = (V, E)}$${\ displaystyle k}$

FRÅGA: finns det en partition av i eller flera ojämna uppsättningar så att var och en är en oberoende uppsättning för och sådan att för varje par av distinkta uppsättningar inte är en oberoende uppsättning.${\ displaystyle V}$${\ displaystyle k}$ ${\ displaystyle V_ {1}, V_ {2}, \ ldots, V_ {k}}$${\ displaystyle V_ {i}}$${\ displaystyle G}$${\ displaystyle V_ {i}, V_ {j}, V_ {i} \ cup V_ {j}}$

Att bestämma det akromatiska talet är NP-svårt ; bestämning om det är större än ett givet antal är NP-komplett , vilket visas av Yannakakis och Gavril 1978 genom transformation från det minsta maximala matchningsproblemet.

Notera att någon färgning av ett diagram med det minsta antalet färger måste vara en komplett färg, så att minimera antalet färger i en komplett färg är bara en upprepning av standard grafen färg problem.

Algoritmer

För vilken som helst fast k är det möjligt att bestämma om det akromatiska talet för en given graf är åtminstone k , i linjär tid.

Optimeringsproblemet tillåter approximation och är ungefärligt inom ett approximationsförhållande . ${\ displaystyle O \ left (| V | / {\ sqrt {\ log | V |}} \ right)}$

Särskilda klasser av grafer

NP-fullständighet av det akromatiska talproblemet gäller även för vissa speciella klasser av grafer: tvåpartsdiagram , komplement till tvåpartsdiagram (det vill säga grafer som inte har någon oberoende uppsättning på mer än två hörn), grafer och intervalldiagram , och även för träd .

För komplement av träd kan det akromatiska antalet beräknas i polynomtid. För träd kan det approximeras till en konstant faktor.

Det akromatiska antalet av en n- dimensionell hyperkubgraf är känd för att vara proportionell mot , men proportionalitetskonstanten är inte känd exakt. ${\ displaystyle {\ sqrt {n2 ^ {n}}}}$

Referenser

externa länkar

• Ett kompendium av NP-optimeringsproblem
• En bibliografi över harmoniska färgämnen och akromatiskt nummer av Keith Edwards