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

DOI10.1016/J.ORL.2005.10.008zbMATH Open1109.05098OpenAlexW1533248588WikidataQ123344904 ScholiaQ123344904MaRDI QIDQ867926FDOQ867926

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

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

zbMATH Keywords

stable setgraph subdivisionlift-and-project

Mathematics Subject Classification ID

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

Cites Work

• On certain polytopes associated with graphs
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Cones of Matrices and Set-Functions and 0–1 Optimization
• The sandwich theorem
• The stable set problem and the lift-and-project ranks of graphs
• On the relationship between disjunctive relaxations and minors in packing and covering problems
• Title not available (Why is that?)

Cited In (7)

• Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs
• Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite 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)