Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
From MaRDI portal
Publication:344830
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
holeschordal graphsproper interval graphscertifying algorithmslinear-timeminimal forbidden induced subgraphsnormal Helly proper circular-arc graphs
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
