Characterization of Chordal Circular-arc Graphs: I Split Graphs
<|reference_start|>Characterization of Chordal Circular-arc Graphs: I Split Graphs: The most elusive problem around the class of circular-arc graphs is identifying all minimal graphs that are not in this class. The main obstacle is the lack of a systematic way of enumerating these minimal graphs. McConnell [FOCS 2001] presented a transformation from circular-arc graphs to interval graphs with certain patterns of representations. We fully characterize these interval patterns for circular-arc graphs that are split graphs, thereby building a connection between minimal split graphs that are not circular-arc graphs and minimal non-interval graphs. This connection enables us to identify all minimal split graphs that are not circular-arc graphs. As a byproduct, we develop a linear-time certifying recognition algorithm for circular-arc graphs when the input is a split graph.<|reference_end|>
@article{cao2024characterization,
    title={Characterization of Chordal Circular-arc Graphs: I. Split Graphs},
    author={Yixin Cao, Jan Derbisz, Tomasz Krawczyk},
    journal={arXiv preprint arXiv:2403.01947},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.01947},
    primaryClass={math.CO cs.DM}
}