Characterisations and Linear-Time Recognition of Probe Cographs

DOI10.1007/978-3-540-74839-7_22zbMath1141.68537OpenAlexW1557893657MaRDI QIDQ3508570

H. N. de Ridder, Van Bang Le

Publication date: 1 July 2008

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74839-7_22

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (9)

Induced betweenness in order-theoretic trees ⋮ The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy ⋮ Probe Ptolemaic Graphs ⋮ The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy ⋮ Recognition of probe proper interval graphs ⋮ A characterization of chain probe graphs ⋮ Certifying algorithms ⋮ Recognition of Probe Ptolemaic Graphs ⋮ Probe threshold and probe trivially perfect graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weakly triangulated graphs
• Probe threshold and probe trivially perfect graphs
• Slim graphs
• On slim graphs, even pairs, and star-cutsets
• On probe interval graphs
• Chordal probe graphs
• 2-tree probe interval graphs have a large obstruction set
• Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs
• Partitioned Probe Comparability Graphs
• A Linear Recognition Algorithm for Cographs
• A good characterization of cograph contractions
• Graph Classes: A Survey
• Forbidden induced subgraph characterization of cograph contractions
• Precoloring Extension III: Classes of Perfect Graphs
• Recognition of Probe Cographs and Partitioned Probe Distance Hereditary Graphs
• STACS 2005
• Computing and Combinatorics
• Theory and Applications of Models of Computation

This page was built for publication: Characterisations and Linear-Time Recognition of Probe Cographs