On Split B1EPG Graphs

Deniz, Zakir
Duzce University, Duzce, Turkey

Nivelle, Simon
ENS Paris Saclay, Paris, France

Ries, Bernard
Université de Fribourg, Fribourg, Switzerland

Schindl, David
Geneva School of Business Administration, Geneva, Switzerland
Show more…
Published in:
 Lecture Notes in Computer Science.  2018, vol. 10807, p. 361375
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

Department
 Département d'informatique

Language


Classification

Computer science

License

License undefined

Identifiers


Persistent URL

https://folia.unifr.ch/unifr/documents/307802
Statistics
Document views: 4
File downloads: