Graph coloring and semidefinite rank

DOI10.1007/978-3-031-06901-7_29MaRDI QIDQ2164723zbMATH OpenOpenAlexFDO

Authors Renee Mirka, Devin Smedira, David P. Williamson

Publication date 16 August 2022

Full work available at URL https://arxiv.org/abs/2202.10515

zbMATH Keywords

sufficiently high rankuniquely colorable planar graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Semidefinite programming (90C22)

Abstract: This paper considers the interplay between semidefinite programming, matrix rank, and graph coloring. Karger, Motwani, and Sudan cite{KMS98} give a vector program for which a coloring of the graph can be encoded as a semidefinite matrix of low rank. By complementary slackness conditions of semidefinite programming, if an optimal dual solution has sufficiently high rank, any optimal primal solution must have low rank. We attempt to characterize graphs for which we can show that the corresponding dual optimal solution must have sufficiently high rank. In the case of the original Karger, Motwani, and Sudan vector program, we show that any graph which is a $k$-tree has sufficiently high dual rank, and we can extract the coloring from the corresponding low-rank primal solution. We can also show that if the graph is not uniquely colorable, then no sufficiently high rank dual optimal solution can exist. This allows us to completely characterize the planar graphs for which dual optimal solutions have sufficiently high dual rank. We then modify the semidefinite program to have an objective function with costs, and explore when we can create a cost function whose optimal dual solution has sufficiently high rank. We show that it is always possible to construct such a cost function given the graph coloring. The construction of the cost function gives rise to a heuristic for graph coloring which we show works well in the case of planar graphs. Our research was motivated by the Colin de Verdi`ere graph invariant cite{CDV90}(and a corresponding conjecture of Colin de Verdi`ere), in which matrices that have some similarities to the dual feasible matrices must have high rank in the case that graphs are of a certain type. We explore the connection between the conjecture and the rank of the dual solutions.

Recommendations

• Approximate graph coloring by semidefinite programming
• scientific article; zbMATH DE number 1256751
• A semidefinite programming-based heuristic for graph coloring
• Semidefinite programming relaxations for graph coloring and maximal clique problems
• On approximate graph colouring and MAX-k-CUT algorithms based on the -function

Cites work

• Algebraic characterization of uniquely vertex colorable graphs
• Approximate graph coloring by semidefinite programming
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Fast generation of planar graphs
• Graph colouring and the probabilistic method
• scientific article; zbMATH DE number 107606 (Why is no real title available?)
• scientific article; zbMATH DE number 1303522 (Why is no real title available?)
• scientific article; zbMATH DE number 1748997 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 3241107 (Why is no real title available?)
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• On the Shannon capacity of a graph
• Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
• The four-colour theorem
• The sandwich theorem

Cited in

(4)

• scientific article; zbMATH DE number 1185595 (Why is no real title available?)
• On low rank-width colorings
• Max cut and semidefinite rank
• Graph coloring and semidefinite rank

This page was built for publication: Graph coloring and semidefinite rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2164723)