Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
Published in:
 Lecture Notes in Computer Science.  2016, vol. 9849, p. 3849
English
We consider the following problem: can a certain graph parameter of some given graph G be reduced by at least d, for some integer d, via at most k graph operations from some specified set S, for some given integer k? As graph parameters we take the chromatic number and the clique number. We let the set S consist of either an edge contraction or a vertex deletion. As all these problems are NPcomplete for general graphs even if d is fixed, we restrict the input graph G to some special graph class. We continue a line of research that considers these problems for subclasses of perfect graphs, but our main results are full classifications, from a computational complexity point of view, for graph classes characterized by forbidding a single induced connected subgraph H.

Faculty
 Faculté des sciences économiques et sociales et du management

Department
 Département d'informatique

Language


Classification

Computer science and technology

License

License undefined

Identifiers


Persistent URL

https://folia.unifr.ch/unifr/documents/307828
Statistics
Document views: 32
File downloads: