A Sum of Squares Characterization of Perfect Graphs
From MaRDI portal
Publication:6087752
DOI10.1137/22m1530410zbMath1527.05076arXiv2110.08950OpenAlexW3207779565MaRDI QIDQ6087752
Publication date: 16 November 2023
Published in: SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2110.08950
semidefinite programmingperfect graphsconvex relaxations for the clique numbermatrix copositivitynonnegative and sum of squares polynomials
Graph polynomials (05C31) Semidefinite programming (90C22) Inequalities for trigonometric functions and polynomials (26D05) Perfect graphs (05C17)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Real zeros for positive semidefinite forms. I
- Spectra of graphs
- Entropy splitting for antiblocking corners and perfect graphs
- Signomial and polynomial optimization via relative entropy and partial dualization
- The strong perfect graph theorem
- Forms derived from the arithmetic-geometric inequality
- Even symmetric sextics
- Graphical properties related to minimal imperfection
- The ellipsoid method and its consequences in combinatorial optimization
- Geometric algorithms and combinatorial optimization
- Extremal positive semidefinite forms
- Combinatorial designs related to the strong perfect graph conjecture
- On certain polytopes associated with graphs
- Partitionable graphs arising from near-factorizations of finite groups
- Progress on perfect graphs
- Cayley partitionable graphs and near-factorizations of finite groups
- Semidefinite programming relaxations for semialgebraic problems
- Sabidussi versus Hedetniemi for three variations of the chromatic number
- Optimization over structured subsets of positive semidefinite matrices via column generation
- Graph imperfection. II
- Minimal imperfect graphs: A simple approach
- The relationships between Wiener index, stability number and clique number of composite graphs
- On sums of squares of \(K\)-nomials
- On the exactness of sum-of-squares approximations for the cone of \(5 \times 5\) copositive matrices
- Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices
- There are significantly more nonnegative polynomials than sums of squares
- A characterization of perfect graphs
- Normal hypergraphs and the perfect graph conjecture
- Generating irreducible copositive matrices using the stable set problem
- On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones
- Global Optimization with Polynomials and the Problem of Moments
- Approximation of the Stability Number of a Graph via Copositive Programming
- Bounds on Entanglement-Assisted Source-Channel Coding via the Lovász \(\vartheta \) Number and Its Variants
- Theta Bodies for Polynomial Ideals
- Gap, cosum and product properties of the θ′ bound on the clique number
- On Sum of Squares Representation of Convex Forms and Generalized Cauchy--Schwarz Inequalities
- Some NP-complete problems in quadratic and nonlinear programming
- A comparison of the Delsarte and Lovász bounds
- On the Shannon capacity of a graph
- Perfect zero–one matrices
- Semidefinite Optimization and Convex Algebraic Geometry
- Refined estimates concerning sumsets contained in the roots of unity
- Finite Convergence of Sum-of-Squares Hierarchies for the Stability Number of a Graph
- Maxima for Graphs and a New Proof of a Theorem of Turán
- DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization
- Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
- Blocking and anti-blocking pairs of polyhedra
- The Lovász Number of Random Graphs
- Sur le coloriage des graphs
- On copositive programming and standard quadratic optimization problems
