• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Critical vertices and edges in H-free graphs

Thumbnail
View/Open
26280.pdf (393.8Kb)
Date
2019
Dewey
Principes généraux des mathématiques
Sujet
vertex deletion; edge contraction; chromatic number
Journal issue
Discrete Applied Mathematics
Volume
257
Publication date
03-2019
Article pages
361-367
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.dam.2018.08.016
URI
https://basepub.dauphine.fr/handle/123456789/20769
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Paulusma, Daniël
Picouleau, Christophe
Ries, Bernard
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Article accepté pour publication ou publié
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.