List Coloring in the Absence of a Linear Forest

DOI10.1007/978-3-642-25870-1_12zbMath1305.05073OpenAlexW1576739559MaRDI QIDQ3104770

Daniël Paulusma, Petr A. Golovach, Jean-François Couturier, Dieter Kratsch

Publication date: 16 December 2011

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/10688/1/10688.pdf

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)

Related Items

4-Coloring H-Free Graphs When H Is Small ⋮ List coloring in the absence of two subgraphs ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ Coloring graphs without short cycles and long induced paths ⋮ On the parameterized complexity of coloring graphs in the absence of a linear forest ⋮ Closing complexity gaps for coloring problems on \(H\)-free graphs ⋮ Coloring Graphs without Short Cycles and Long Induced Paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
• Some new hereditary classes where graph coloring remains NP-hard
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Dominating cliques in \(P_ 5\)-free graphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Generalized coloring for tree-like graphs
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Vertex colouring and forbidden subgraphs -- a survey
• On the complexity of 4-coloring graphs without long induced paths
• 4-Coloring H-Free Graphs When H Is Small
• Colouring Vertices of Triangle-Free Graphs
• Three Complexity Results on Coloring P k -Free Graphs
• A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
• The NP-Completeness of Edge-Coloring
• Graph colorings with local constraints -- a survey
• NP completeness of finding the chromatic index of regular graphs