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

DOI10.1016/j.dam.2015.08.023zbMath1350.05104arXiv1405.0329OpenAlexW2964304438MaRDI QIDQ344830

Luciano N. Grippo, Yixin Cao, 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)

Related Items

Essential obstacles to Helly circular-arc graphs ⋮ On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid ⋮ Unit interval editing is fixed-parameter tractable ⋮ Canonical representations for circular-arc graphs using flip sets

Cites Work

• Unnamed Item
• Unnamed Item
• Certifying algorithms
• A simpler linear-time recognition of circular-arc graphs
• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
• The clique operator on circular-arc graphs
• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Linear-time recognition of circular-arc graphs
• 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
• Representation of a finite graph by a set of intervals on the real line
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• Coloring a Family of Circular Arcs
• Independent Sets in Circular-Arc Graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm