scientific article; zbMATH DE number 1496606

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

graph decompositions\(\beta \)-perfect graphssignable graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)

Related Items

Structure and algorithms for (cap, even hole)-free graphs, 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, 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 Class of Three‐Colorable Triangle‐Free Graphs, Even-hole-free graphs part I: Decomposition theorem, Stable sets and graphs with no even holes, Unnamed Item, A faster algorithm to recognize even-hole-free graphs

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