Essential obstacles to Helly circular-arc graphs (Q2166233)

The intersection graph of a set \(\mathcal{A}\) of arcs on a circle is any graph isomorphic to the one having \(\mathcal{A}\) as the vertex set and with an edge between two arcs whenever they intersect. A circular-arc graph \(G\) is an intersection graph of some set \(\mathcal{A}\) of arcs on a circle; such a set \(\mathcal{A}\) is also called a circular-arc model of the graph \(G\). A Helly circular-arc graph is a circular-arc graph that has a circular-arc model satisfying the Helly property: every nonempty subfamily that is pairwise intersecting has a nonempty total intersection. \textit{B. L. Joeris} et al. [Algorithmica 59, No. 2, 215--239 (2011; Zbl 1209.68376)] characterized Helly circular-arc graphs to be precisely those circular-arc graphs that do not contain any induced subgraph belonging to the family of graphs called obstacles. However, the family of obstacles is neither minimal -- since there exist obstacles that are induced subgraphs of other obstacles -- nor contained in the family of circular-arc graphs. This naturally raises the question of characterizing the minimal circular-arc obstacles. \textit{F. Bonomo} et al. [Discrete Math. Theor. Comput. Sci. 16, No. 3, 1--22 (2014; Zbl 1294.05079)] produced a partial list of these graphs. In this paper, the author introduces a refinement of the notion of obstacle, called essential obstacle, and proves that the minimal forbidden induced circular-arc subgraphs for the class of Helly circular-arc graphs are precisely the essential obstacles. Furthermore, it is shown that, given any obstacle, one can find in linear time a minimal forbidden induced subgraph for the class of Helly circular-arc graphs contained in it as an induced subgraph. In particular, using the linear time certifying algorithm of \textit{B. L. Joeris} et al. [Algorithmica 59, No. 2, 215--239 (2011; Zbl 1209.68376)], one can also obtain in linear time a minimal negative certificate for input as any circular-arc graph that is not a Helly circular-arc graph. It is an open problem to find a forbidden induced subgraph characterization for the class of Helly circular-arc graphs, i.e.\ not restricted only to circular-arc graphs. As a partial answer, the author obtains 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, it is shown that one can find in linear time an induced claw, an induced \(5\)-wheel, or an induced minimal forbidden induced subgraph for the class of Helly circular-arc graphs in any given graph that is not a Helly circular-arc graph.