A Sum of Squares Characterization of Perfect Graphs
From MaRDI portal
Publication:6087752
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.
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
Cites work
- scientific article; zbMATH DE number 3150484 (Why is no real title available?)
- scientific article; zbMATH DE number 3851153 (Why is no real title available?)
- scientific article; zbMATH DE number 3717357 (Why is no real title available?)
- scientific article; zbMATH DE number 3593686 (Why is no real title available?)
- scientific article; zbMATH DE number 3634289 (Why is no real title available?)
- scientific article; zbMATH DE number 3435574 (Why is no real title available?)
- scientific article; zbMATH DE number 3002670 (Why is no real title available?)
- scientific article; zbMATH DE number 1490041 (Why is no real title available?)
- scientific article; zbMATH DE number 753805 (Why is no real title available?)
- scientific article; zbMATH DE number 850230 (Why is no real title available?)
- A characterization of perfect graphs
- A comparison of the Delsarte and Lovász bounds
- Approximation of the stability number of a graph via copositive programming
- Blocking and anti-blocking pairs of polyhedra
- Bounds on Entanglement-Assisted Source-Channel Coding via the Lovász \(\vartheta \) Number and Its Variants
- Cayley partitionable graphs and near-factorizations of finite groups
- Combinatorial designs related to the strong perfect graph conjecture
- Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
- DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
- Entropy splitting for antiblocking corners and perfect graphs
- Even symmetric sextics
- Extremal positive semidefinite forms
- Finite convergence of sum-of-squares hierarchies for the stability number of a graph
- Forms derived from the arithmetic-geometric inequality
- Gap, cosum and product properties of the \(\theta ^{\prime}\) bound on the clique number
- Generating irreducible copositive matrices using the stable set problem
- Geometric algorithms and combinatorial optimization
- Global optimization with polynomials and the problem of moments
- Graph imperfection. II
- Graphical properties related to minimal imperfection
- Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices
- Maxima for Graphs and a New Proof of a Theorem of Turán
- Minimal imperfect graphs: A simple approach
- Moments, positive polynomials and their applications
- Normal hypergraphs and the perfect graph conjecture
- On Sum of Squares Representation of Convex Forms and Generalized Cauchy--Schwarz Inequalities
- On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones
- On certain polytopes associated with graphs
- On copositive programming and standard quadratic optimization problems
- On sums of squares of \(K\)-nomials
- On the Shannon capacity of a graph
- On the exactness of sum-of-squares approximations for the cone of \(5 \times 5\) copositive matrices
- Optimization over structured subsets of positive semidefinite matrices via column generation
- Partitionable graphs arising from near-factorizations of finite groups
- Perfect zero–one matrices
- Progress on perfect graphs
- Random graphs.
- Real zeros for positive semidefinite forms. I
- Refined estimates concerning sumsets contained in the roots of unity
- Sabidussi versus Hedetniemi for three variations of the chromatic number
- Semidefinite Optimization and Convex Algebraic Geometry
- Semidefinite programming relaxations for semialgebraic problems
- Signomial and polynomial optimization via relative entropy and partial dualization
- Some NP-complete problems in quadratic and nonlinear programming
- Spectra of graphs
- Sums of squares, moment matrices and optimization over polynomials
- Sur le coloriage des graphs
- The Lovász Number of Random Graphs
- The ellipsoid method and its consequences in combinatorial optimization
- The relationships between Wiener index, stability number and clique number of composite graphs
- The strong perfect graph theorem
- There are significantly more nonnegative polynomials than sums of squares
- Theta bodies for polynomial ideals
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)
