A Sum of Squares Characterization of Perfect Graphs
From MaRDI portal
Publication:6087752
DOI10.1137/22M1530410zbMATH Open1527.05076arXiv2110.08950OpenAlexW3207779565MaRDI QIDQ6087752FDOQ6087752
Authors: Amir Ali Ahmadi, Cemil Dibek 
Publication date: 16 November 2023
Published in: SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)
Abstract: We present an algebraic characterization of perfect graphs, i.e., graphs for which the clique number and the chromatic number coincide for every induced subgraph. We show that a graph is perfect if and only if certain nonnegative polynomials associated with the graph are sums of squares. As a byproduct, we obtain several infinite families of nonnegative polynomials that are not sums of squares through graph-theoretic constructions. We also characterize graphs for which the associated polynomials belong to certain structured subsets of sum of squares polynomials. Finally, we reformulate some well-known results from the theory of perfect graphs as statements about sum of squares proofs of nonnegativity of certain polynomials.
Full work available at URL: https://arxiv.org/abs/2110.08950
Recommendations
- On perfectness of sums of graphs
- A new characterization of perfect graphs
- Sum-perfect graphs
- scientific article; zbMATH DE number 3891424
- A new characterization of trivially perfect graphs
- A characterization of \(\Gamma\alpha(k)\)-perfect graphs
- A note on perfect graphs
- A characterization of \(b\)-perfect graphs
- A characterization of domination perfect graphs
- Some conjectures on perfect graphs
semidefinite programmingperfect graphsconvex relaxations for the clique numbermatrix copositivitynonnegative and sum of squares polynomials
Semidefinite programming (90C22) Graph polynomials (05C31) Perfect graphs (05C17) Inequalities for trigonometric functions and polynomials (26D05)
Cites Work
- Title not available (Why is that?)
- Some NP-complete problems in quadratic and nonlinear programming
- Title not available (Why is that?)
- Spectra of graphs
- Geometric algorithms and combinatorial optimization
- Normal hypergraphs and the perfect graph conjecture
- Global optimization with polynomials and the problem of moments
- On the Shannon capacity of a graph
- Sur le coloriage des graphs
- Even symmetric sextics
- The ellipsoid method and its consequences in combinatorial optimization
- On certain polytopes associated with graphs
- Progress on perfect graphs
- Semidefinite programming relaxations for semialgebraic problems
- A characterization of perfect graphs
- Random graphs.
- Approximation of the stability number of a graph via copositive programming
- Moments, positive polynomials and their applications
- Sums of squares, moment matrices and optimization over polynomials
- Title not available (Why is that?)
- Semidefinite Optimization and Convex Algebraic Geometry
- Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
- The strong perfect graph theorem
- Forms derived from the arithmetic-geometric inequality
- Extremal positive semidefinite forms
- Title not available (Why is that?)
- 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
- Real zeros for positive semidefinite forms. I
- Blocking and anti-blocking pairs of polyhedra
- Bounds on Entanglement-Assisted Source-Channel Coding via the Lovász \(\vartheta \) Number and Its Variants
- A comparison of the Delsarte and Lovász bounds
- Perfect zero–one matrices
- Title not available (Why is that?)
- On copositive programming and standard quadratic optimization problems
- Theta bodies for polynomial ideals
- Entropy splitting for antiblocking corners and perfect graphs
- Title not available (Why is that?)
- Combinatorial designs related to the strong perfect graph conjecture
- The relationships between Wiener index, stability number and clique number of composite graphs
- Title not available (Why is that?)
- There are significantly more nonnegative polynomials than sums of squares
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Gap, cosum and product properties of the \(\theta ^{\prime}\) bound on the clique number
- The Lovász Number of Random Graphs
- Partitionable graphs arising from near-factorizations of finite groups
- Graphical properties related to minimal imperfection
- Signomial and polynomial optimization via relative entropy and partial dualization
- Finite convergence of sum-of-squares hierarchies for the stability number of a graph
- On the exactness of sum-of-squares approximations for the cone of \(5 \times 5\) copositive matrices
- Graph imperfection. II
- Minimal imperfect graphs: A simple approach
- Optimization over structured subsets of positive semidefinite matrices via column generation
- Cayley partitionable graphs and near-factorizations of finite groups
- Sabidussi versus Hedetniemi for three variations of the chromatic number
- On sums of squares of \(K\)-nomials
- Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices
- Refined estimates concerning sumsets contained in the roots of unity
- Generating irreducible copositive matrices using the stable set problem
- On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones
- On Sum of Squares Representation of Convex Forms and Generalized Cauchy--Schwarz Inequalities
Cited In (4)
This page was built for publication: A Sum of Squares Characterization of Perfect Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087752)
