|
 
|
[PRP16] Reducing the clique and chromatic number via edge contractions and vertex deletions
Conférence Internationale avec comité de lecture : ISCO 2016 - 4th International Symposium on Combinatorial Optimization, April 2016, pp.38-49, Series LNCS9849, Salerne, Italie,Mots clés: graph, contraction, deletion, chromatic number, clique
Résumé:
We consider the following problem: can a certain graph pa- rameter of some given graph G be reduced by at least d, for some inte- ger 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 classifica- tions, from a computational complexity point of view, for graph classes characterized by forbidding a single induced connected subgraph H.
Collaboration:
LAMSADE
BibTeX
| @inproceedings { | |||
| PRP16, | |||
| title | = | "{Reducing the clique and chromatic number via edge contractions and vertex deletions}", | |
| author | = | " C. Picouleau and B. Ries and D. Paulusma ", | |
| booktitle | = | "{ISCO 2016 - 4th International Symposium on Combinatorial Optimization}", | |
| year | = | 2016, | |
| month | = | "April", | |
| series | = | "LNCS9849", | |
| pages | = | "38-49", | |
| address | = | "Salerne, Italie", | |
| } | |||
