FoCM 2014 conference
Workshop A4 - Graph Theory and Combinatorics
December 12, 17:30 ~ 18:00 - Room B11
Characterizing and Recognizing Normal Helly Circular-Arc Graphs
Luciano Grippo
Instituto de Ciencias, Universidad Nacional de General Sarmiento, Argentina - lgrippo@ungs.edu.ar
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 problems of determining the remaining minimal forbidden induced subgraphs and finding a direct recognition algorithm. In this work, we solve their problems, obtaining the complete list of minimal forbidden induced subgraphs for the class of normal Helly circular-arc graphs, and presenting a direct recognition algorithm which also finds, in linear time, when the input is a normal Helly circular-arc graph, a minimal forbidden induced subgraph as certificate.
Joint work with Yixin Cao (Department of Computing, Hong Kong Polytechnic University) and Martín Darío Safe (Instituto de Ciencias, Universidad Nacional de General Sarmiento).