Autor:	Cao, Yixin, Krawczyk, Tomasz
Rok vydání:	2024
Předmět:	Mathematics - Combinatorics Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	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. Comment: arXiv admin note: text overlap with arXiv:2403.01947
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2408.10892 Zobrazit plný text záznamu View this record from Arxiv