Three Complexity Results on Coloring P k -Free Graphs

DOI10.1007/978-3-642-10217-2_12zbMath1267.05113OpenAlexW2175372374WikidataQ60488711 ScholiaQ60488711MaRDI QIDQ3651537

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

Publication date: 11 December 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-10217-2_12

zbMATH Keywords

computational complexitygraph coloring\(P _{k }\)-free graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

4-Coloring H-Free Graphs When H Is Small ⋮ Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time ⋮ On the parameterized complexity of coloring graphs in the absence of a linear forest ⋮ List coloring in the absence of a linear forest ⋮ Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs ⋮ Colouring Vertices of Triangle-Free Graphs ⋮ Coloring Graphs without Short Cycles and Long Induced Paths ⋮ Updating the complexity status of coloring graphs without a fixed induced linear forest ⋮ Colouring vertices of triangle-free graphs without forests ⋮ List Coloring in the Absence of a Linear Forest ⋮ Algorithms and almost tight results for 3-colorability of small diameter graphs

This page was built for publication: Three Complexity Results on Coloring P k -Free Graphs