Graph coloring and semidefinite rank

DOI10.1007/S10107-024-02085-0zbMATH Open1545.05076MaRDI QIDQ6589762FDOQ6589762

Authors: Renee Mirka, Devin Smedira, David P. Williamson 

Publication date: 20 August 2024

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Recommendations

• Graph coloring and semidefinite rank
• Approximate graph coloring by semidefinite programming
• Semidefinite programming relaxations for graph coloring and maximal clique problems
• A semidefinite programming-based heuristic for graph coloring
• On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function

zbMATH Keywords

optimizationsemidefinite programminggraph coloring

Mathematics Subject Classification ID

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

Cites Work

• Approximate graph coloring by semidefinite programming
• On the Shannon capacity of a graph
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Fast generation of planar graphs
• Title not available (Why is that?)
• The four-colour theorem
• Title not available (Why is that?)
• The sandwich theorem
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Title not available (Why is that?)
• Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
• Title not available (Why is that?)
• Algebraic characterization of uniquely vertex colorable graphs
• How false is Kempe's proof of the four color theorem? II

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 Q6589762)