Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs

DOI10.1137/050637091zbMath1141.05037OpenAlexW2009862268WikidataQ56430103 ScholiaQ56430103MaRDI QIDQ3519195

Marina Lipshteyn, Anne Berry, 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

triangulationperfect graphchordal graphelimination schemebicoloringprobe graph

Mathematics Subject Classification ID

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

Related Items (15)

Adjacency matrices of probe interval graphs ⋮ The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy ⋮ Characterisations and Linear-Time Recognition of Probe Cographs ⋮ Recognition of probe proper interval graphs ⋮ A characterization of chain probe graphs ⋮ Partitioned probe comparability graphs ⋮ Path-bicolorable graphs ⋮ Recognition of Probe Ptolemaic Graphs ⋮ On the bi-enhancement of chordal-bipartite probe graphs ⋮ The sandwich problem for decompositions and almost monotone properties ⋮ Regularity of binomial edge ideals of chordal graphs ⋮ The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs ⋮ Probe threshold and probe trivially perfect graphs ⋮ Path-Bicolorable Graphs ⋮ 2-tree probe interval graphs have a large obstruction set

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