|
 
|
[PRP17] Reducing the Chromatic Number by Vertex or Edge Deletions
Conférence Internationale avec comité de lecture : LAGOS, September 2017, Vol. 62, pp.243-248, Series ENDM, France, (DOI: doi.org/10.1016/j.endm.2017.10.042)Mots clés: Graphe, Coloration
Résumé:
A vertex or edge in a graph is critical if its deletion reduces the chromatic number of the graph by~1.
A graph is vertex-critical if every vertex is critical and edge-critical if every edge is critical.
To increase our understanding of the graph coloring problem, vertex-critical and edge-critical graphs have been studied intensively. We consider the problems of testing whether a graph has a critical vertex or edge, respectively.
We give a complete classification of the complexity of both problems for $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~1.
Hence, we obtain the same classification for the problem of testing if a graph has an edge whose contraction reduces
the chromatic number by~1.
As a consequence of our results, we are also able to complete the complexity classification of the more general vertex deletion and edge contraction blocker problems for $H$-free graphs
when the graph parameter is the chromatic number.
Collaboration:
LAMSADE
BibTeX
| @inproceedings { | |||
| PRP17, | |||
| title | = | "{Reducing the Chromatic Number by Vertex or Edge Deletions}", | |
| author | = | " C. Picouleau and B. Ries and D. Paulusma ", | |
| booktitle | = | "{LAGOS}", | |
| year | = | 2017, | |
| month | = | "September", | |
| series | = | "ENDM", | |
| volume | = | 62, | |
| pages | = | "243-248", | |
| address | = | " France", | |
| doi | = | "doi.org/10.1016/j.endm.2017.10.042", | |
| } | |||
