Decomposition of even-hole-free graphs with star cutsets and 2-joins

DOI10.1016/j.jctb.2012.10.001zbMath1257.05136OpenAlexW1995521164WikidataQ59902173 ScholiaQ59902173MaRDI QIDQ1932477

Kristina Vušković, Murilo V. G. da Silva

Publication date: 18 January 2013

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2012.10.001

zbMATH Keywords

decompositionrecognition algorithmeven-hole-free graphsstar cutsets2-joins

Mathematics Subject Classification ID

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

Related Items (11)

Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree ⋮ The (theta, wheel)-free graphs. II: Structure theorem ⋮ A note on coloring \((4K_1, C_4, C_6)\)-free graphs with a \(C_7\) ⋮ Finding a shortest even hole in polynomial time ⋮ On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs ⋮ Coloring \((4K_1,C_4,C_6)\)-free graphs ⋮ Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs ⋮ On the forbidden induced subgraph sandwich problem ⋮ Vertex elimination orderings for hereditary graph classes ⋮ Unnamed Item ⋮ A faster algorithm to recognize even-hole-free graphs

This page was built for publication: Decomposition of even-hole-free graphs with star cutsets and 2-joins