Forbidden induced subgraphs of normal Helly circular-arc graphs: Characterization and detection

Yixin Cao, Luciano N. Grippo, Martín D. Safe

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 Citations (Scopus)

Abstract

A normal Helly circular-arc graph is the intersection graph of a set of arcs on a circle of which no three or less arcs cover the whole circle. Lin et al. (2013) characterized circular-arc graphs that are not normal Helly circular-arc graphs, and used them to develop the first recognition algorithm for this graph class. As open problems, they ask for the forbidden subgraph characterization and a direct recognition algorithm for normal Helly circular-arc graphs, both of which are resolved by the current paper. Moreover, when the input is not a normal Helly circular-arc graph, our recognition algorithm finds in linear time a minimal forbidden induced subgraph as a certificate. Our approach yields also a considerably simpler algorithm for the certifying recognition of proper Helly circular-arc graphs, a subclass of normal Helly circular-arc graphs.
Original languageEnglish
Pages (from-to)67-83
Number of pages17
JournalDiscrete Applied Mathematics
Volume216
DOIs
Publication statusPublished - 10 Jan 2017

Keywords

  • (minimal) forbidden induced subgraphs
  • (normal, Helly, proper) circular-arc models
  • (proper) interval graphs
  • Certifying algorithms
  • Chordal graphs
  • Holes
  • Linear-time

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this