
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
Type
Article accepté pour publication ou publiéDate
2019Journal name
Discrete Applied MathematicsVolume
257Publisher
Elsevier
Pages
361-367
Publication identifier
Metadata
Show full item recordAuthor(s)
Paulusma, DaniëlPicouleau, Christophe

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 numberRelated items
Showing items related by title and author.
-
Diner, Öznur Yaşar; Paulusma, Daniël; Picouleau, Christophe; Ries, Bernard (2018) Article accepté pour publication ou publié
-
Ries, Bernard; Picouleau, Christophe; Paulusma, Daniël; Diner, Öznur (2015) Communication / Conférence
-
Bernard Ries; Picouleau, Christophe; de Werra, Dominique; Costa, Marie-Christine; Bentz, Cédric (2009) Article accepté pour publication ou publié
-
Bentz, Cédric; Costa, Marie-Christine; Ries, Bernard; de Werra, Dominique; Picouleau, Christophe; Zenklusen, Rico (2010) Article accepté pour publication ou publié
-
Bentz, Cédric; Costa, Marie-Christine; Picouleau, Christophe; Ries, Bernard; de Werra, Dominique (2012) Article accepté pour publication ou publié