Minimal N_+-rank graphs: progress on Lipták and Tunçel's conjecture

DOI10.1016/J.ORL.2005.10.008MaRDI QIDQ867926zbMATH OpenOpenAlexWikidataFDO

Authors Mariana S. Escalante, M. S. Montelar, G. Nasini

Publication date 19 February 2007

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2005.10.008

zbMATH Keywords

graph subdivisionlift-and-projectstable set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Minimal \(k\)-connected graphs with small number of vertices of degree \(k\)
• On the graph complement conjecture for minimum rank
• Neighbor-connected graphs and projective planes
• Graphs whose minimal rank is two
• Fractional minimal rank

Cites work

• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Cones of Matrices and Set-Functions and 0–1 Optimization
• scientific article; zbMATH DE number 2230211 (Why is no real title available?)
• On certain polytopes associated with graphs
• On the relationship between disjunctive relaxations and minors in packing and covering problems
• The sandwich theorem
• The stable set problem and the lift-and-project ranks of graphs

Cited in

(9)

• Some advances on Lovász-Schrijver semidefinite programming relaxations of the fractional stable set polytope
• Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs
• Lovász-Schrijver PSD-operator on claw-free graphs
• Near-perfect graphs with polyhedral N_+(G)
• Characterizing N_+-perfect line graphs
• Lovász and Schrijver N_+-relaxation on web graphs
• Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
• On rank-monotone graph operations and minimal obstruction graphs for the Lovász-Schrijver SDP hierarchy
• Stable set polytopes with high lift-and-project ranks for the Lovász-Schrijver SPD operator

This page was built for publication: Minimal \(N_{+}\)-rank graphs: progress on Lipták and Tunçel's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q867926)