Algorithms for Perfectly Contractile Graphs
From MaRDI portal
Publication:5470779
DOI10.1137/S0895480104442522zbMath1094.05028arXiv1309.0435OpenAlexW1996804679MaRDI QIDQ5470779
Frédéric Maffray, Nicolas Trotignon
Publication date: 1 June 2006
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1309.0435
Related Items
Detecting a long even hole ⋮ Even pairs in square-free Berge graphs ⋮ The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs ⋮ Finding a shortest even hole in polynomial time ⋮ On the forbidden induced subgraph sandwich problem ⋮ Coloring square-free Berge graphs ⋮ The three-in-a-tree problem ⋮ The structure of (theta, pyramid, 1‐wheel, 3‐wheel)‐free graphs ⋮ CIO and ring graphs: deficiency and testing ⋮ Even pairs and prism corners in square-free Berge graphs ⋮ Detecting induced subgraphs ⋮ Finding induced trees ⋮ A structure theorem for graphs with no cycle with a unique chord and its consequences ⋮ The sandwich problem for decompositions and almost monotone properties ⋮ Claw-Free $t$-Perfect Graphs Can Be Recognized in Polynomial Time ⋮ Coloring Artemis graphs ⋮ Unnamed Item ⋮ A faster algorithm to recognize even-hole-free graphs