Some new hereditary classes where graph coloring remains NP-hard
type: Item
instance of: scholarly article
title: Some new hereditary classes where graph coloring remains NP-hard
zbMATH Open document ID: 1063.05050
published in: Discrete Mathematics
publication date: 2005-06-23T00:00:00Z
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 2181969
zbMATH Keywords: Line graph
zbMATH Keywords: Induced subgraph
zbMATH Keywords: Partial subgraph
author: David Schindl
MaRDI profile type: Publication
full work available at URL: j.disc.2005.03.003
OpenAlex ID: W1964063859
cites work: Polynomial algorithm for finding the largest independent sets in graphs without forks
cites work: Q5615282
cites work: On the stability number of claw-free \(P_5\)-free and more general graphs
cites work: The strong perfect graph theorem
cites work: Edmonds polytopes and a hierarchy of combinatorial problems
cites work: Stable sets in two subclasses of banner-free graphs
cites work: Geometric algorithms and combinatorial optimization
cites work: Finding augmenting chains in extensions of claw-free graphs
cites work: Q4448764
cites work: Stable sets in certain \(P_6\)-free graphs
cites work: Q4770411
DOI: 10.1016/J.DISC.2005.03.003
Recommended article: Hereditary graph classes: When the complexities of <scp>coloring</scp> and <scp>clique cover</scp> coincide
Recommended article: Q5075768
Recommended article: Complexity of \(C_k\)-coloring in hereditary classes of graphs
Recommended article: Hereditarily hard \(H\)-colouring problems
Recommended article: Q4272117
Recommended article: Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
Recommended article: New hardness results for graph and hypergraph colorings
Recommended article: On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size
Recommended article: Q5874504
Recommended article: Q3012403
description: scientific article; zbMATH DE number 2181969