Välfärgad graf
Inom grafteori , ett underfält av matematik, är en välfärgad graf en oriktad graf för vilken girig färgning använder samma antal färger oavsett i vilken ordning färgerna väljs för dess hörn. Det vill säga för dessa grafer är det kromatiska antalet (minsta antal färger) och Grundy-talet (maximalt antal girigt valda färger) lika.
Exempel
De välfärgade graferna inkluderar de fullständiga graferna och cykelgraferna med udda längd (graferna som utgör undantagsfallen till Brooks sats ) såväl som de fullständiga tvådelade graferna och kompletta flerdelade graferna .
Det enklaste exemplet på en graf som inte är välfärgad är en bana med fyra vertex. Att färglägga hörnen i banordning använder två färger, det optimala för denna graf. Men att färga ändarna av banan först (med samma färg för varje ände) gör att den giriga färgningsalgoritmen använder tre färger för denna graf. Eftersom det finns en icke-optimal vertexordning är banan inte välfärgad.
Komplexitet
En graf är välfärgad om och endast om den inte har två hörnordningar för vilka den giriga färgningsalgoritmen producerar olika antal färger. Därför kan att känna igen icke-välfärgade grafer utföras inom komplexitetsklassen NP . Å andra sidan har en graf Grundy-nummer eller mer om och endast om grafen som erhålls från genom att lägga till en -vertex klick är välfärgad. Därför, genom en minskning från Grundy-nummerproblemet, är det NP-komplett att testa om dessa två beställningar existerar. Det följer att det är co-NP-komplett att testa om en given graf är välfärgad.
Relaterade egenskaper
En graf är ärftligt välfärgad om varje inducerad subgraf är välfärgad. De ärftligt välfärgade graferna är exakt kograferna, de grafer som inte har en fyrkantig bana som en inducerad subgraf.