2-tree probe interval graphs have a large obstruction set

DOI10.1016/J.DAM.2004.06.015MaRDI QIDQ2565858zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Nataša Pržulj, Derek G. Corneil

Publication date 28 September 2005

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2004.06.015

Mathematics Subject Classification ID

Trees (05C05) Structural characterization of families of graphs (05C75) Applications of graph theory (05C90) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20)

Recommendations

• A characterization of 2-tree probe interval graphs
• A characterization of cycle-free unit probe interval graphs
• On probe interval graphs
• Probe interval and probe unit interval graphs on superclasses of cographs
• Probe interval graphs and probe unit interval graphs on superclasses of cographs

Cites work

• A characterization of cycle-free unit probe interval graphs
• A polynomial time recognition algorithm for probe interval graphs
• Characterizations for unit interval bigraphs
• Chordal probe graphs (extended abstract)
• Faster Subtree Isomorphism
• scientific article; zbMATH DE number 1735726 (Why is no real title available?)
• scientific article; zbMATH DE number 1933220 (Why is no real title available?)
• scientific article; zbMATH DE number 2119749 (Why is no real title available?)
• scientific article; zbMATH DE number 1439437 (Why is no real title available?)
• On probe interval graphs
• Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Two tricks to triangulate chordal probe graphs in polynomial time

Cited in

(7)

• A characterization of cycle-free unit probe interval graphs
• Characterizing interval graphs which are probe unit interval graphs
• Recognition of probe proper interval graphs
• A characterization of 2-tree probe interval graphs
• Probe interval and probe unit interval graphs on superclasses of cographs
• Characterisations and Linear-Time Recognition of Probe Cographs
• A characterization of chain probe graphs

Describes a project that uses

Uses Software

• nauty

This page was built for publication: 2-tree probe interval graphs have a large obstruction set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2565858)