Lov?sz-Schrijver PSD-operator and the stable set polytope of claw-free graphs

被引：2

作者：

Bianchi, Silvia M. ^{[1
]}

Escalante, Mariana S. ^{[2
]}

Nasini, Graciela L. ^{[2
]}

Wagler, Annegret K. ^{[3
]}

机构：

[1] Univ Nacl Rosario, FCEIA, Rosario, Argentina

[2] Univ Nacl Rosario, CONICET & FCEIA, Rosario, Argentina

[3] Univ Clermont Auvergne, LIMOS UMR CNRS 6158, Clermont Ferrand, France

来源：

DISCRETE APPLIED MATHEMATICS | 2023年 / 332卷

关键词：

Semidefinite relaxation; Stable set problem; Claw-free graphs; IMPERFECTION RATIO; RANK FACETS; ALGORITHM;

D O I：

10.1016/j.dam.2023.01.012

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The subject of this work is the study of LS+-perfect graphs defined as those graphs G for which the stable set polytope STAB(G) is achieved in one iteration of Lovasz-Schrijver PSD-operator LS+, applied to its edge relaxation ESTAB(G). The recently formulated LS+ -Perfect Graph Conjecture aims at a characterization of this family of graphs, through the structure of the facet defining inequalities of the stable set polytope. The main contribution of this work is to verify it for the well-studied class of claw-free graphs.(c) 2023 Elsevier B.V. All rights reserved.

引用

页码：70 / 86

页数：17

共 47 条

[1] Berge C., 1963, Six Papers on Graph Theory, P1
[2] Lovasz-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
Bianchi, S.
Escalante, M.
Nasini, G.
Tuncel, L.
[J]. MATHEMATICAL PROGRAMMING, 2017, 162 (1-2) : 201 - 223
[3] Bianchi S., 2016, ANN LATIN IBEROAMERI
[4] Bianchi S., 2016, BORDEAUX GRAPH WORKS, P29
[5] Bianchi S. M., 2011, ELECT NOTES DISCRETE, V37, P393
[6] Lovasz-Schrijver PSD-Operator on Claw-Free Graphs
Bianchi, Silvia
Escalante, Mariana
Nasini, Graciela
Wagler, Annegret
[J]. COMBINATORIAL OPTIMIZATION, ISCO 2016, 2016, 9849 : 59 - 70
[7] Bianchi SM., 2013, Electron. Notes Discret. Math, V44, P339, DOI [10.1016/j.endm.2013.10.053, DOI 10.1016/J.ENDM.2013.10.053]
[8] Claw-free graphs. V. Global structure
Chudnovsky, Maria
Seymour, Paul
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2008, 98 (06) : 1373 - 1410
[9] The strong perfect graph theorem
Chudnovsky, Maria
Robertson, Neil
Seymour, Paul
Thomas, Robin
[J]. ANNALS OF MATHEMATICS, 2006, 164 (01) : 51 - 229
[10] CERTAIN POLYTOPES ASSOCIATED WITH GRAPHS
CHVATAL, V
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1975, 18 (02) : 138 - 154

← 1 2 3 4 5 →