En graf är H-fri om den inte innehåller en inducerad subgraph isomorphic till grafen H. Grafen P k betecknar en sökväg på k hörn. Problemet - coloring är problemet att avgöra om en graf kan färgas med de flesta färger så att angränsande hörn får olika färger. Vi visar att 4-färgning är NP-komplett för P8-fria grafer. Detta förbättrar ett resultat av Le, Randerath och Schiermeyer, som visade att 4-färgning är NP-komplett för P9-fria grafer, och ett resultat av Woeginger och Sgall, som visade att 5-färgning är NP-komplett för P8-fria grafer. Dessutom bevisar vi att precoloring förlängning version av 4-färgning är NP-komplett för P7-fria grafer, men att precoloring förlängning version av 3-färgning kan lösas i polynom tid för (P2 + P4)-fria grafer, en subklass av P7-fria grafer. Här betecknar P2 + P4 den osammanhängande föreningen mellan en P2 och en P4. Vi betecknar uppdelningen av s kopior av en P3 av sP3 och involverar Ramsey nummer för att bevisa att precoloring förlängning version av 3-färgning kan lösas i polynom tid för sP3-fria grafer för alla fasta s. Kombinera våra två senaste resultat med kända resultat ger en fullständig komplexitet klassificering av (precoring förlängning av) 3-färgning
Senare, Broersma m.fl. REF förlängde detta resultat genom att visa att 3-PRECOLORING EXTENSION kan lösas i polynom tid för H-fria grafer om H är en linjär skog på högst 6 hörn.
Updating the complexity status of coloring graphs without a fixed induced linear forest
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}