Characterization of Circular-arc Graphs: II. McConnell Flipping
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915264798392320 |
|---|---|
| author | Cao, Yixin Krawczyk, Tomasz |
| author_facet | Cao, Yixin Krawczyk, Tomasz |
| contents | McConnell [FOCS 2001] presented a flipping transformation from circular-arc graphs to interval graphs with certain patterns of representations. Beyond its algorithmic implications, this transformation is instrumental in identifying all minimal graphs that are not circular-arc graphs. We conduct a structural study of this transformation, and for $C_{4}$-free graphs, we achieve a complete characterization of these patterns. This characterization allows us, among other things, to identify all minimal chordal graphs that are not circular-arc graphs in a companion paper. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_10892 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Characterization of Circular-arc Graphs: II. McConnell Flipping Cao, Yixin Krawczyk, Tomasz Combinatorics Data Structures and Algorithms McConnell [FOCS 2001] presented a flipping transformation from circular-arc graphs to interval graphs with certain patterns of representations. Beyond its algorithmic implications, this transformation is instrumental in identifying all minimal graphs that are not circular-arc graphs. We conduct a structural study of this transformation, and for $C_{4}$-free graphs, we achieve a complete characterization of these patterns. This characterization allows us, among other things, to identify all minimal chordal graphs that are not circular-arc graphs in a companion paper. |
| title | Characterization of Circular-arc Graphs: II. McConnell Flipping |
| topic | Combinatorics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.10892 |