|
 
|
[BBP15] Blockers for the stability number and the chromatic number
Revue Internationale avec comité de lecture : Journal Graphs and Combinatorics, vol. 31(1), pp. 73-90, 2015, (doi:10.1007/s00373-013-1380-2)Mots clés: Blocker, chromatic number, stability number, bipartite graph, split graph, threshold graph.
Résumé:
Given an undirected graph G = (V,E) and two positive integers k and d, we are interested in finding a set of edges (resp. non-edges) of size at most k to delete (resp. to add) in such a way that the chromatic number (resp. stability number) in the resulting graph will decrease by at least d compared to the original graph. We investigate these two problems in various classes of graphs (split graphs, threshold graphs, (complement of) bipartite graphs) and determine their computational complexity. In some of the polynomial-time solvable cases, we also give a structural description of a solution.
Equipe:
oc
Collaboration:
LAMSADE
BibTeX
| @article { | |||
| BBP15, | |||
| title | = | "{Blockers for the stability number and the chromatic number}", | |
| author | = | "C. Bazgan and C. Bentz and C. Picouleau and B. Ries", | |
| journal | = | "Graphs and Combinatorics", | |
| year | = | 2015, | |
| volume | = | 31, | |
| number | = | 1, | |
| pages | = | "73-90", | |
| doi | = | "10.1007/s00373-013-1380-2", | |
| } | |||
