On Split B1-EPG 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
-
2018
Published in:
- Lecture Notes in Computer Science. - 2018, vol. 10807, p. 361-375
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 NP-complete 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
-
- English
- Classification
- Computer science and technology
- License
- License undefined
- Identifiers
-
- RERO DOC 324625
- DOI 10.1007/978-3-319-77404-6_27
- Persistent URL
- https://folia.unifr.ch/unifr/documents/307802
Statistics
Document views: 21
File downloads:
- b1-epg_rero.pdf: 56