Probe split graphs

zbMATH Open1153.05324MaRDI QIDQ5387698FDOQ5387698

Authors: Van Bang Le, H. N. de Ridder 

Publication date: 27 May 2008

Full work available at URL: https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/issue/view/85/showToc.html

Recommendations

• Probe threshold and probe trivially perfect graphs
• Probe Ptolemaic Graphs
• Characterisations and Linear-Time Recognition of Probe Cographs
• Recognition of Probe Cographs and Partitioned Probe Distance Hereditary Graphs
• Computing and Combinatorics

zbMATH Keywords

recognition algorithmsvertex partitionprobe split graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (16)

• Block-graph width
• Bisplit graphs
• Characterisations and Linear-Time Recognition of Probe Cographs
• Computing and Combinatorics
• Probe Ptolemaic Graphs
• Recognition of split-graphic sequences
• Adjacency matrices of probe interval graphs
• Probe threshold and probe trivially perfect graphs
• Probe interval and probe unit interval graphs on superclasses of cographs
• The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy
• Characterizing and recognizing probe block graphs
• A characterization of chain probe graphs
• On two variants of split graphs: 2-unipolar graph and \(k\)-probe-split graph
• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
• An algorithmic characterization of splitting signed graph
• Minimal obstructions for a matrix partition problem in chordal graphs

This page was built for publication: Probe split graphs

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