• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Critical vertices and edges in H-free graphs

Paulusma, Daniël; Picouleau, Christophe; Ries, Bernard (2019), Critical vertices and edges in H-free graphs, Discrete Applied Mathematics, 257, p. 361-367. 10.1016/j.dam.2018.08.016

View/Open
26280.pdf (393.8Kb)
Type
Article accepté pour publication ou publié
Date
2019
Journal name
Discrete Applied Mathematics
Volume
257
Publisher
Elsevier
Pages
361-367
Publication identifier
10.1016/j.dam.2018.08.016
Metadata
Show full item record
Author(s)
Paulusma, Daniël

Picouleau, Christophe cc

Ries, Bernard
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
A vertex or edge in a graph is critical if its deletion reduces the chromatic number of the graph by one. We consider the problems of deciding whether a graph has a critical vertex or edge, respectively. We give a complexity dichotomy for both problems restricted to H-free graphs, that is, graphs with no induced subgraph isomorphic to H. Moreover, we show that an edge is critical if and only if its contraction reduces the chromatic number by one. Hence, we also obtain a complexity dichotomy for the problem of deciding if a graph has an edge whose contraction reduces the chromatic number by one.
Subjects / Keywords
vertex deletion; edge contraction; chromatic number

Related items

Showing items related by title and author.

  • Thumbnail
    Contraction and deletion blockers for perfect graphs and H-free graphs 
    Diner, Öznur Yaşar; Paulusma, Daniël; Picouleau, Christophe; Ries, Bernard (2018) Article accepté pour publication ou publié
  • Thumbnail
    Contraction Blockers for Graphs with Forbidden Induced Paths 
    Ries, Bernard; Picouleau, Christophe; Paulusma, Daniël; Diner, Öznur (2015) Communication / Conférence
  • Thumbnail
    Degree-constrained edge partitionings in graphs arising from discrete tomography 
    Bernard Ries; Picouleau, Christophe; de Werra, Dominique; Costa, Marie-Christine; Bentz, Cédric (2009) Article accepté pour publication ou publié
  • Thumbnail
    Blockers and transversalsnext term in some previous termsubclasses of bipartite graphs: When caterpillars are dancing on a gridnext term 
    Bentz, Cédric; Costa, Marie-Christine; Ries, Bernard; de Werra, Dominique; Picouleau, Christophe; Zenklusen, Rico (2010) Article accepté pour publication ou publié
  • Thumbnail
    d-Transversals of stable sets and vertex covers in weighted bipartite graphs 
    Bentz, Cédric; Costa, Marie-Christine; Picouleau, Christophe; Ries, Bernard; de Werra, Dominique (2012) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo