2024/09/04 by Cao, Yixin, Krawczyk, Tomasz
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2409.02733
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á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.