2014/02/11 by Luciano N. Grippo, Grippo, Luciano N., Martín D. Safe +1
Computer Science · Engineering · #05C62 #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #VLSI and FPGA Design Techniques #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1402.2641
openalex publication_date 2014/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An interval graph is the intersection graph of a finite set of intervals on a line and a circular-arc graph is the intersection graph of a finite set of arcs on a circle. While a forbidden induced subgraph characterization of interval graphs was found fifty years ago, finding an analogous characterization for circular-arc graphs is a long-standing open problem. In this work, we study the intersection graphs of finite sets of arcs on a circle no three of which cover the circle, known as normal Helly circular-arc graphs. Those circular-arc graphs which are minimal forbidden induced subgraphs for the class of normal Helly circular-arc graphs were identified by Lin, Soulignac, and Szwarcfiter, who also posed the problem of determining the remaining minimal forbidden induced subgraphs. In this work, we solve their problem, obtaining the complete list of minimal forbidden induced subgraphs for the class of normal Helly circular-arc graphs.