Decomposition of odd-hole-free graphs by double star cutsets and 2-joins

DOI10.1016/S0166-218X(03)00364-0zbMath1043.05096OpenAlexW4235847069WikidataQ57950152 ScholiaQ57950152MaRDI QIDQ1827853

Kristina Vušković, Michele Conforti, Cornuéjols, Gérard

Publication date: 6 August 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(03)00364-0

zbMATH Keywords

2-joinDecompositionDouble star cutsetEven-signable graphsOdd-hole-free graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

One-three join: a graph operation and its consequences, Detecting 2-joins faster, Hereditary Efficiently Dominatable Graphs, Graphs of separability at most 2, Substitution and \(\chi\)-boundedness, Decomposing Berge graphs and detecting balanced skew partitions, Singularity Degree of the Positive Semidefinite Matrix Completion Problem, Combinatorial optimization with 2-joins, A polynomial recognition algorithm for balanced matrices, A faster algorithm to recognize even-hole-free graphs

Cites Work

• Perfect graphs, partitionable graphs and cutsets
• The strong perfect graph theorem
• Star-cutsets and perfect graphs
• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs
• Compositions for perfect graphs
• Even-hole-free graphs part I: Decomposition theorem
• Even-hole-free graphs part II: Recognition algorithm
• A mickey-mouse decomposition theorem