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

DOI10.1016/J.DAM.2015.08.023zbMATH Open1350.05104arXiv1405.0329OpenAlexW2964304438MaRDI QIDQ344830FDOQ344830

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)

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.

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

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

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)

Cites Work

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

Cited In (6)

• Unit interval editing is fixed-parameter tractable
• Essential obstacles to Helly circular-arc graphs
• On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
• Modification problems toward proper (Helly) circular-arc graphs
• Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
• 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)