Critical vertices and edges in H-free graphs
- Paulusma, Daniël Durham University
- Picouleau, Christophe Conservatoire National des Arts et Métiers
- Ries, Bernard University of Fribourg
-
2019
Published in:
- Discrete applied mathematics. - 2019, vol. 257, p. 361-367
English
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.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Economics
- License
- License undefined
- Identifiers
-
- RERO DOC 324550
- DOI 10.1016/j.dam.2018.08.016
- Persistent URL
- https://folia.unifr.ch/unifr/documents/307799
Statistics
Document views: 68
File downloads:
- critical_rero.pdf: 243