Partial characterizations of circle graphs
2011, Discrete applied mathematics 159 (16), 1699-1706, 2011Citas: 12
Agregar PDF Importar citas SCRAPME Plots Conexiones
Autor(es)
Flavia Bonomo and Guillermo Durán and Luciano N Grippo and Martín D Safe
Abstract
A circle graph is the intersection graph of a family of chords on a circle. There is no known characterization of circle graphs by forbidden induced subgraphs that do not involve the notions of local equivalence or pivoting operations. We characterize circle graphs by a list of minimal forbidden induced subgraphs when the graph belongs to one of the following classes: linear domino graphs, P4-tidy graphs, and tree-cographs. We also completely characterize by minimal forbidden induced subgraphs the class of unit Helly circle graphs, which are those circle graphs having a model whose chords have all the same length, are pairwise different, and satisfy the Helly property.
Plot de citas
Citas
| # | Title | Year | Source | Authors | |
|---|---|---|---|---|---|
| 1 | Structural results on circular-arc graphs and circle graphs: a survey and the main open problems | 2014 | Discrete Applied Mathematics | G Durán, LN Grippo, MD Safe | |
| 2 | Complexity aspects of the Helly property: Graphs and hypergraphs | 2012 | The Electronic Journal of … | MC Dourado, F Protti | |
| 3 | On nested and 2-nested graphs: two subclasses of graphs between threshold and split graphs | 2019 | arXiv preprint arXiv … | N Pardal, GA Durán, LN Grippo, MD Safe | |
| 4 | Structural characterization of some problems on circle and interval graphs | 2020 | arXiv preprint arXiv:2006.00099 | N Pardal | |
| 5 | Forbidden induced subgraph characterization of circle graphs within split graphs | 2022 | Discrete Applied … | F Bonomo-Braberman, G Durán, N Pardal | |
| 6 | Notes on a theorem of Naji | 2017 | Discrete Mathematics | L Traldi | |
| 7 | 2-nested matrices: towards understanding the structure of circle graphs | 2022 | Graphs and Combinatorics | G Durán, N Pardal, MD Safe | |
| 8 | Intersection of longest paths in graph theory and predicting performance in facial recognition | 2017 | NA | A Yates | |
| 9 | Splitting cubic circle graphs | 2015 | arXiv preprint arXiv:1504.01143 | L Traldi | |
| 10 | Structural results on circular-arc graphs and circle graphs: A survey and the main open problems | 2014 | NA | G Durán Maggiolo, LN Grippo, MD Safe | |
| 11 | Caracterización estructural de algunos problemas en grafos circle y de intervalos | 2020 | NA | N Pardal | |
| 12 | Caractérisation structurelle de quelques problèmes dans les graphes de cordes et d'intervalles | 2020 | NA | N Pardal |