On circular-arc graphs having a model with no three arcs covering the circle

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.
Comment: 15 pages, 3 figures. This paper originally appeared in proceedings of the XVI Congreso Latino-Iberoamericano de Investigaci\'on Operativa and the XLIV Simp\'osio Brasileiro de Pesquisa Operacional, September 24-28, 2012, Rio de Janeiro, Brazil. Anais do XLIV Simposio Brasileiro de Pesquisa Operacional, SOBRAPO, Rio de Janeiro, Brazil, 2012, pages 4093--4104. http://www.din.uem.br/sbpo/sbpo2012/pdf/arq0518.pdf