Essential obstacles to Helly circular-arc graphs

Abstract

A Helly circular-arc graph is the intersection graph of a set of arcs on a circle having the Helly property. We introduce essential obstacles, which are a refinement of the notion of obstacles, and prove that essential obstacles are precisely the minimal forbidden induced circular-arc subgraphs for the class of Helly circular-arc graphs. We show that it is possible to find in linear time, in any given obstacle, some minimal forbidden induced subgraph for the class of Helly circular-arc graphs contained as an induced subgraph. Moreover, relying on an existing linear-time algorithm for finding induced obstacles in circular-arc graphs, we conclude that it is possible to find in linear time an induced essential obstacle in any circular-arc graph that is not a Helly circular-arc graph. The problem of finding a forbidden induced subgraph characterization, not restricted only to circular-arc graphs, for the class of Helly circular-arc graphs remains unresolved. As a partial answer to this problem, we find the minimal forbidden induced subgraph characterization for the class of Helly circular-arc graphs restricted to graphs containing no induced claw and no induced 5-wheel. Furthermore, we show that there is a linear-time algorithm for finding, in any given graph that is not a Helly circular-arc graph, an induced subgraph isomorphic to claw, 5-wheel, or some minimal forbidden induced subgraph for the class of Helly circular-arc graphs.