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.0329MaRDI 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
holes; chordal graphs; proper interval graphs; certifying algorithms; linear-time; minimal forbidden induced subgraphs; normal Helly proper circular-arc graphs
05C85: Graph algorithms (graph-theoretic aspects)
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Related Items
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, Essential obstacles to Helly circular-arc graphs
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
