On the bi-enhancement of chordal-bipartite probe graphs

DOI10.1016/J.IPL.2009.12.003MaRDI QIDQ991750zbMATH OpenOpenAlexFDO

Authors Elad Cohen, Martin Charles Golumbic, Marina Lipshteyn, Michal Stern

Publication date 7 September 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2009.12.003

zbMATH Keywords

combinatorial problemschordal bipartite graphsprobe graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Recommendations

• Chordal probe graphs (extended abstract)
• On cycle- and bi-cycle extendability in chordal and chordal bipartite graphs
• Several results on chordal bipartite graphs
• Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs
• Two characterizations of chain partitioned probe graphs
• A \(k\)-partite generalization of chordal bipartite graphs
• A characterization of chain probe graphs
• Chordal bipartite graphs of bounded tree- and clique-width
• Representation characterizations of chordal bipartite graphs
• Chordal bipartite, strongly chordal, and strongly chordal bipartite graphs

Cites work

• scientific article; zbMATH DE number 1735726 (Why is no real title available?)
• scientific article; zbMATH DE number 2117210 (Why is no real title available?)
• scientific article; zbMATH DE number 2119749 (Why is no real title available?)
• A characterization of chain probe graphs
• A note on finding all homogeneous set sandwiches
• A polynomial time recognition algorithm for probe interval graphs
• Chordal probe graphs
• Computing and Combinatorics
• Graph Sandwich Problems
• On probe interval graphs
• Perfect Elimination and Chordal Bipartite Graphs
• Probe threshold and probe trivially perfect graphs
• Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs
• The complexity of comparability graph recognition and coloring
• The pair completion algorithm for the homogeneous set sandwich problem

Cited in

(5)

• Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs
• Characterizing and recognizing probe block graphs
• A characterization of chain probe graphs
• Two characterizations of chain partitioned probe graphs
• Good characterizations and linear time recognition for 2-probe block graphs

This page was built for publication: On the bi-enhancement of chordal-bipartite probe graphs

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