A Sum of Squares Characterization of Perfect Graphs

Amir Ali Ahmadi, Cemil Dibek

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)685-715
Number of pages31
JournalSIAM Journal on Applied Algebra and Geometry
Volume7
Issue number4
DOIs
StatePublished - 2023

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

Fingerprint

Dive into the research topics of 'A Sum of Squares Characterization of Perfect Graphs'. Together they form a unique fingerprint.

Cite this