Publication:4500707

DOI<204::AID-JGT2>3.0.CO;2-P 10.1002/1097-0118(200007)34:3<204::AID-JGT2>3.0.CO;2-PzbMath0953.05061MaRDI QIDQ4500707

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

Publication date: 23 January 2001

zbMATH Keywords

graph decompositions; \(\beta \)-perfect graphs; signable graphs

Mathematics Subject Classification ID

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

05C75: Structural characterization of families of graphs

05C85: Graph algorithms (graph-theoretic aspects)

05C17: Perfect graphs

Related Items

A Class of Three‐Colorable Triangle‐Free Graphs, Unnamed Item, Finding a shortest even hole in polynomial time, (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels, (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth, Stable sets and graphs with no even holes, Structure and algorithms for (cap, even hole)-free graphs, A note on chromatic number of (cap, even hole)-free graphs, A better upper bound on the chromatic number of (cap, even-hole)-free graphs, A faster algorithm to recognize even-hole-free graphs, Even-hole-free graphs part I: Decomposition theorem

Cites Work

• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• On the complexity of testing for odd holes and induced odd paths
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Structural properties and decomposition of linear balanced matrices
• Decomposition of balanced matrices
• \(\beta\)-perfect graphs
• Even and odd holes in cap-free graphs