Vi bevisar tre komplexa resultat på vertex färgproblem begränsade till P k - fria grafer, dvs. grafer som inte innehåller en väg på k hörn som en inducerad subgraf. Först och främst visar vi att den pre-coloring förlängningsversionen av 5-färgning förblir NP-komplett när den begränsas till P 6 -fria grafer. Senaste resultaten av Hoàng et al. antyder att detta problem är polynomiskt solvable på P 5 - fria grafer. För det andra visar vi att den pre-färgning förlängning version av 3-färgning är polynomiskt lösbar för P 6 -fria grafer. Detta innebär en enklare algoritm för att kontrollera 3-färgbarheten av P 6 -fria grafer än algoritmen som ges av Randerath och Schiermeyer. Slutligen bevisar vi att 6-färgning är NP-komplett för P 7 -fria grafer. Detta problem var känt för att vara polynomiskt solvable för P 5 -fria grafer och NP-komplett för P 8 -fria grafer, så det finns fortfarande ett öppet fall.
Ett resultat som generaliserades av Broersma et al. REF som visade att 3-PRECOLORING EXTENSION kan lösas i polynom tid för P 6 -fria grafer.
Three Complexity Results on Coloring P k -Free Graphs
{'venue': 'IWOCA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}