  


A Sum of Squares Characterization of Perfect Graphs
Amir Ali Ahmadi(aaaprinceton.edu) 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 graphtheoretic constructions. We also characterize graphs for which the associated polynomials belong to certain structured subsets of sum of squares polynomials. Finally, we reformulate some wellknown results from the theory of perfect graphs as statements about sum of squares proofs of nonnegativity of certain polynomials. Keywords: Nonnegative and sum of squares polynomials, perfect graphs, matrix copositivity, semidefinite programming, convex relaxations for the clique number Category 1: Combinatorial Optimization Category 2: Linear, Cone and Semidefinite Programming Category 3: Convex and Nonsmooth Optimization Citation: Download: [PDF] Entry Submitted: 10/17/2021 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  