Three complexity results on coloring \(P_k\)-free graphs

DOI10.1016/j.ejc.2011.12.008zbMath1257.05037OpenAlexW2159829425WikidataQ60488525 ScholiaQ60488525MaRDI QIDQ1933643

Daniël Paulusma, Fedor V. Fomin, Hajo J. Broersma, Petr A. Golovach

Publication date: 24 January 2013

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2011.12.008

zbMATH Keywords

polynomial-time algorithmdominating cliquepre-colouring extensionpath free graphspolymial solvabilityvertex colouring problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (24)

A new characterization of \(P_k\)-free graphs ⋮ 4-colorability of \(P_6\)-free graphs ⋮ Complexity of coloring graphs without paths and cycles ⋮ Partitioning \(H\)-free graphs of bounded diameter ⋮ Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter ⋮ 4-coloring \((P_6, \text{bull})\)-free graphs ⋮ Colouring \((P_r + P_s)\)-free graphs ⋮ Certifying coloring algorithms for graphs without long induced paths ⋮ Independent feedback vertex sets for graphs of bounded diameter ⋮ 3-coloring \(C_4\) or \(C_3\)-free diameter two graphs ⋮ 3-colouring \(P_t\)-free graphs without short odd cycles ⋮ 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Improved complexity results on \(k\)-coloring \(P_t\)-free graphs ⋮ Two complexity results for the vertex coloring problem ⋮ Closing complexity gaps for coloring problems on \(H\)-free graphs ⋮ Constructions of \(k\)-critical \(P_5\)-free graphs ⋮ Colouring graphs of bounded diameter in the absence of small cycles ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Colouring graphs of bounded diameter in the absence of small cycles ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ On list \(k\)-coloring convex bipartite graphs ⋮ Colouring (P_r+P_s)-Free Graphs ⋮ On coloring a class of claw-free and hole-twin-free graphs

This page was built for publication: Three complexity results on coloring \(P_k\)-free graphs