Three complexity results on coloring \(P_k\)-free graphs
Publication:1933643
DOI10.1016/j.ejc.2011.12.008zbMath1257.05037WikidataQ60488525 ScholiaQ60488525MaRDI QIDQ1933643
Daniël Paulusma, Fedor V. Fomin, Petr A. Golovach, Hajo J. Broersma
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
polynomial-time algorithm; dominating clique; pre-colouring extension; path free graphs; polymial solvability; vertex colouring problems
68Q25: Analysis of algorithms and problem complexity
05C35: Extremal problems in graph theory
05C38: Paths and cycles
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)