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

DOI10.1016/J.DAM.2015.08.023MaRDI QIDQ344830zbMATH OpenOpenAlexFDO

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

Publication date 24 November 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.0329

zbMATH Keywords

holeschordal graphsproper interval graphscertifying algorithmslinear-timeminimal forbidden induced subgraphsnormal Helly proper circular-arc graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: A normal Helly circular-arc graph is the intersection graph of arcs on a circle of which no three or less arcs cover the whole circle. Lin, Soulignac, and Szwarcfiter [Discrete Appl. Math. 2013] characterized circular-arc graphs that are not normal Helly circular-arc graphs, and used it to develop the first recognition algorithm for this graph class. As open problems, they ask for the forbidden induced 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 certificate.

Recommendations

• Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
• Normal Helly circular-arc graphs and its subclasses
• Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
• Linear-time recognition of Helly circular-arc models and graphs
• Essential obstacles to Helly circular-arc graphs

Cites work

• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A simpler linear-time recognition of circular-arc graphs
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• Certifying algorithms
• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Coloring a Family of Circular Arcs
• Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
• Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
• Independent Sets in Circular-Arc Graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• Linear-time recognition of circular-arc graphs
• Normal Helly circular-arc graphs and its subclasses
• On finding Tucker submatrices and Lekkerkerker-Boland subgraphs
• Representation of a finite graph by a set of intervals on the real line
• Restricted circular-arc graphs and clique cycles
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• Structure theorems for some circular-arc graphs
• The clique operator on circular-arc graphs

Cited in

(6)

• Modification problems toward proper (Helly) circular-arc graphs
• Essential obstacles to Helly circular-arc graphs
• Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
• On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
• Normal Helly circular-arc graphs and its subclasses
• Canonical representations for circular-arc graphs using flip sets

This page was built for publication: Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344830)