Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs

DOI10.1137/050637091MaRDI QIDQ3519195zbMATH OpenOpenAlexWikidataFDO

Authors Anne Berry, Marina Lipshteyn, Martin Charles Golumbic

Publication date 13 August 2008

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/c49a8b42b2dd81da9a66d465a8d3b72ad4706d50

zbMATH Keywords

bicoloringchordal graphelimination schemeperfect graphprobe graphtriangulation

Mathematics Subject Classification ID

Perfect graphs (05C17) Structural characterization of families of graphs (05C75)

Recommendations

• Chordal probe graphs
• Chordal probe graphs (extended abstract)
• Two tricks to triangulate chordal probe graphs in polynomial time
• Partitioned Probe Comparability Graphs
• On the bi-enhancement of chordal-bipartite probe graphs

Cited in

(20)

• Probe threshold and probe trivially perfect graphs
• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
• The sandwich problem for decompositions and almost monotone properties
• Chordal probe graphs
• Regularity of binomial edge ideals of chordal graphs
• Recognition of probe proper interval graphs
• 2-tree probe interval graphs have a large obstruction set
• Recognition of Probe Ptolemaic Graphs
• Characterisations and Linear-Time Recognition of Probe Cographs
• Path-bicolorable graphs. (Extended abstract)
• Two tricks to triangulate chordal probe graphs in polynomial time
• The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs
• Chordal probe graphs (extended abstract)
• Adjacency matrices of probe interval graphs
• A characterization of chain probe graphs
• Path-bicolorable graphs
• Finding d-cuts in probe H-free graphs
• First-order logic with metric betweenness – the case of non-definability of some graph classes
• Partitioned probe comparability graphs
• On the bi-enhancement of chordal-bipartite probe graphs

This page was built for publication: Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs

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