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

stable setgraph subdivisionlift-and-project

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

• scientific article; zbMATH DE number 2230211 (Why is no real title available?)
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Cones of Matrices and Set-Functions and 0–1 Optimization
• 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

(7)

• Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
• Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs
• Lovász and Schrijver \(N_+\)-relaxation on web graphs
• Lovász-Schrijver PSD-operator on claw-free graphs
• Characterizing \(N_+\)-perfect line graphs
• Near-perfect graphs with polyhedral \(N_+(G)\)
• Some advances on Lovász-Schrijver semidefinite programming relaxations of the fractional stable set polytope

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)