Some new hereditary classes where graph coloring remains NP-hard

DOI10.1016/j.disc.2005.03.003zbMath1063.05050OpenAlexW1964063859MaRDI QIDQ556851

David Schindl

Publication date: 23 June 2005

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2005.03.003

zbMATH Keywords

Induced subgraphLine graphPartial subgraph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (18)

4-Coloring H-Free Graphs When H Is Small ⋮ List coloring in the absence of two subgraphs ⋮ Vertex coloring of graphs with few obstructions ⋮ Colouring diamond-free graphs ⋮ Colouring square-free graphs without long induced paths. ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ A coloring algorithm for \(4 K_1\)-free line graphs ⋮ On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs ⋮ Coloring graphs without short cycles and long induced paths ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ The coloring problem for classes with two small obstructions ⋮ Adaptive linear combination of heuristic orderings in constructing examination timetables ⋮ List coloring in the absence of a linear forest ⋮ Two cases of polynomial-time solvability for the coloring problem ⋮ Colouring vertices of triangle-free graphs without forests ⋮ List Coloring in the Absence of a Linear Forest ⋮ Colouring square-free graphs without long induced paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strong perfect graph theorem
• Finding augmenting chains in extensions of claw-free graphs
• Geometric algorithms and combinatorial optimization
• On the stability number of claw-free \(P_5\)-free and more general graphs
• Stable sets in certain \(P_6\)-free graphs
• Stable sets in two subclasses of banner-free graphs
• Edmonds polytopes and a hierarchy of combinatorial problems
• Polynomial algorithm for finding the largest independent sets in graphs without forks

This page was built for publication: Some new hereditary classes where graph coloring remains NP-hard