Grundy nummer
I grafteori är Grundy -talet eller Grundy-kromatiska numret för en oriktad graf det maximala antalet färger som kan användas av en girig färgstrategi som beaktar grafens hörn i följd och tilldelar varje vertex sin första tillgängliga färg, med hjälp av en vertex beställning valt att använda så många färger som möjligt. Grundy-nummer är uppkallade efter PM Grundy , som studerade ett analogt koncept för riktade grafer 1939. Den oriktade versionen introducerades av Christen & Selkow (1979) .
Exempel
Till exempel, för en väggraf med fyra hörn, är det kromatiska talet två men Grundy-talet är tre: om de två ändpunkterna på banan färgläggs först, kommer den giriga färgningsalgoritmen att använda tre färger för hela grafen.
Atomer
Zaker (2006) definierar en sekvens av grafer som kallas t - atomer , med egenskapen att en graf har ett Grundy-tal minst t om och endast om den innehåller en t -atom. Varje t -atom bildas av en oberoende mängd och en ( t − 1) -atom, genom att addera en kant från varje vertex av ( t − 1) -atomen till en vertex i den oberoende mängden, på ett sådant sätt att varje medlem av den oberoende uppsättningen har minst en kant som hänför sig till den. En Grundy-färgning av en t -atom kan erhållas genom att först färga den oberoende mängden med den minsta numrerade färgen och sedan färga den återstående ( t − 1) -atomen med ytterligare t − 1- färger. Till exempel är den enda 1-atomen en enda vertex, och den enda 2-atomen är en enda kant, men det finns två möjliga 3-atomer: en triangel och en fyrkantsbana.
I glesa grafer
För en graf med n hörn och degeneration d är Grundy-talet O ( d log n ) . Speciellt för grafer av gränsad degeneration (såsom plana grafer ) eller grafer för vilka det kromatiska talet och degenerationen är avgränsade inom konstanta faktorer för varandra (såsom kordagrafer ) är Grundy-talet och det kromatiska talet inom en logaritmisk faktor för varje Övrig. För intervallgrafer är det kromatiska talet och Grundy-talet inom en faktor 8 från varandra.
Beräkningskomplexitet
Att testa om Grundy-talet för en given graf är minst k , för en fast konstant k , kan utföras i polynomtid , genom att söka efter alla möjliga k -atomer som kan vara subgrafer till den givna grafen. Denna algoritm är dock inte följsam med fasta parametrar , eftersom exponenten i sin körtid beror på k . När k är en indatavariabel snarare än en parameter, är problemet NP-komplett . Grundy-talet är högst ett plus den maximala graden av grafen, och det förblir NP-komplett för att testa om det är lika med ett plus den maximala graden. Det finns en konstant c > 1 så att det är NP-svårt under randomiserade reduktioner att approximera Grundy-talet till ett approximationsförhållande bättre än c .
Det finns en exakt exponentiell tidsalgoritm för Grundy-talet som löper i tiden O (2.443 n ) .
För träd och grafer med begränsad trädbredd kan Grundy-talet vara obegränsat stort. Ändå kan Grundy-talet beräknas i polynomtid för träd och är trakterbart med fasta parametrar när det parametriseras av både trädbredden och Grundy-talet, även om beroendet av trädbredden ( förutsatt att den exponentiella tidshypotesen antas ) måste vara större än enstaka exponentiella. När det parametriseras av Grundy-numret självt, kan det beräknas i fast-parameter traktabel tid för ackordsgrafer och klofria grafer, och även (med hjälp av allmänna resultat om subgrafisomorfism i glesa grafer för att söka efter atomer) för grafer med begränsad expansion .
Välfärgade grafer
En graf kallas välfärgad om dess Grundy-tal är lika med dess kromatiska tal. Att testa om en graf är välfärgad är coNP-komplett. De ärftligt välfärgade graferna (grafer för vilka varje inducerad subgraf är välfärgad) är exakt kograferna , de grafer som inte har en väg med fyra vertex som en inducerad subgraf.