Show simple item record

dc.contributor.authorBazgan, Cristina*
dc.contributor.authorBentz, Cédric*
dc.contributor.authorPicouleau, Christophe*
dc.contributor.authorRies, Bernard*
dc.date.accessioned2013-11-18T10:40:47Z
dc.date.available2013-11-18T10:40:47Z
dc.date.issued2015
dc.identifier.issn0911-0119
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/12091
dc.language.isoenen
dc.subjectbipartite graph
dc.subjectblocker
dc.subjectchromatic number
dc.subjectstability number
dc.subjectsplit graph
dc.subjectThreshold graph
dc.subject.ddc003
dc.titleBlockers for the stability number and the chromatic number
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherConservatoire national des Arts et Métiers (Paris);France
dc.contributor.editoruniversityotherUniversité Paris-Sud (Orsay);France
dc.description.abstractenGiven 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.
dc.relation.isversionofjnlnameGraphs and Combinatorics
dc.relation.isversionofjnlvol31
dc.relation.isversionofjnlissue1
dc.relation.isversionofjnldate2015
dc.relation.isversionofjnlpages73-90
dc.relation.isversionofdoi10.1007/s00373-013-1380-2
dc.relation.isversionofjnlpublisherSpringer
dc.subject.ddclabelRecherche opérationnelle
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-01-05T14:36:59Z
hal.person.labIds989*
hal.person.labIds439315*
hal.person.labIds439315*
hal.person.labIds989*
hal.faultCode{"duplicate-entry":{"hal-01505546":{"doi":"1.0"}}}


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record