Characterization of Circular-arc Graphs: III Chordal Graphs
<|reference_start|>Characterization of Circular-arc Graphs: III Chordal Graphs: We identify all minimal chordal graphs that are not circular-arc graphs, thereby resolving one of ``the main open problems'' concerning the structures of circular-arc graphs as posed by Dur{\'{a}}n, Grippo, and Safe in 2011. The problem had been attempted even earlier, and previous efforts have yielded partial results, particularly for claw-free graphs and graphs with an independence number of at most four. The answers turn out to have very simple structures: all the nontrivial ones belong to a single family. Our findings are based on a structural study of McConnell's flipping, which transforms circular-arc graphs into interval graphs with certain representation patterns.<|reference_end|>
@article{cao2024characterization,
    title={Characterization of Circular-arc Graphs: III. Chordal Graphs},
    author={Yixin Cao and Tomasz Krawczyk},
    journal={arXiv preprint arXiv:2409.02733},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.02733},
    primaryClass={math.CO cs.DM}
}