Contractions in perfect graph
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914649359777792 |
|---|---|
| author | Dupont-Bouillard, Alexandre Fouilhoux, Pierre Grappe, Roland Lacroix, Mathieu |
| author_facet | Dupont-Bouillard, Alexandre Fouilhoux, Pierre Grappe, Roland Lacroix, Mathieu |
| contents | In this paper, we characterize the class of {\em contraction perfect} graphs which are the graphs that remain perfect after the contraction of any edge set. We prove that a graph is contraction perfect if and only if it is perfect and the contraction of any single edge preserves its perfection. This yields a characterization of contraction perfect graphs in terms of forbidden induced subgraphs, and a polynomial algorithm to recognize them. We also define the utter graph $u(G)$ which is the graph whose stable sets are in bijection with the co-2-plexes of $G$, and prove that $u(G)$ is perfect if and only if $G$ is contraction perfect. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_12793 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Contractions in perfect graph Dupont-Bouillard, Alexandre Fouilhoux, Pierre Grappe, Roland Lacroix, Mathieu Combinatorics Discrete Mathematics In this paper, we characterize the class of {\em contraction perfect} graphs which are the graphs that remain perfect after the contraction of any edge set. We prove that a graph is contraction perfect if and only if it is perfect and the contraction of any single edge preserves its perfection. This yields a characterization of contraction perfect graphs in terms of forbidden induced subgraphs, and a polynomial algorithm to recognize them. We also define the utter graph $u(G)$ which is the graph whose stable sets are in bijection with the co-2-plexes of $G$, and prove that $u(G)$ is perfect if and only if $G$ is contraction perfect. |
| title | Contractions in perfect graph |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2401.12793 |