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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 685-715 |
| Number of pages | 31 |
| Journal | SIAM Journal on Applied Algebra and Geometry |
| Volume | 7 |
| Issue number | 4 |
| DOIs | |
| State | Published - 2023 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Algebra and Number Theory
- Geometry and Topology
- Applied Mathematics
Keywords
- convex relaxations for the clique number
- matrix copositivity
- nonnegative and sum of squares polynomials
- perfect graphs
- semidefinite programming