## 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