Skip to main content

Research Repository

Advanced Search

Critical vertices and edges in H-free graphs

Paulusma, D.; Picouleau, C.; Ries, B.

Critical vertices and edges in H-free graphs Thumbnail


Authors

C. Picouleau

B. Ries



Abstract

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 -free graphs, that is, graphs with no induced subgraph isomorphic to . 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.

Citation

Paulusma, D., Picouleau, C., & Ries, B. (2019). Critical vertices and edges in H-free graphs. Discrete Applied Mathematics, 257, 361-367. https://doi.org/10.1016/j.dam.2018.08.016

Journal Article Type Article
Acceptance Date Aug 28, 2018
Online Publication Date Oct 11, 2018
Publication Date Mar 31, 2019
Deposit Date Sep 19, 2018
Publicly Available Date Mar 29, 2024
Journal Discrete Applied Mathematics
Print ISSN 0166-218X
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 257
Pages 361-367
DOI https://doi.org/10.1016/j.dam.2018.08.016
Public URL https://durham-repository.worktribe.com/output/1314370

Files





You might also like



Downloadable Citations