• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Blockers for the stability number and the chromatic number

Thumbnail
View/Open
GC.pdf (202.2Kb)
Date
2015
Dewey
Recherche opérationnelle
Sujet
bipartite graph; blocker; chromatic number; stability number; split graph; Threshold graph
Journal issue
Graphs and Combinatorics
Volume
31
Number
1
Publication date
2015
Article pages
73-90
Publisher
Springer
DOI
http://dx.doi.org/10.1007/s00373-013-1380-2
URI
https://basepub.dauphine.fr/handle/123456789/12091
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Bazgan, Cristina
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Bentz, Cédric
status unknown
Picouleau, Christophe
status unknown
Ries, Bernard
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Article accepté pour publication ou publié
Abstract (EN)
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.