Graph coloring and semidefinite rank

DOI10.1007/S10107-024-02085-0MaRDI QIDQ6589762zbMATHFDO

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)

zbMATH Keywords

optimizationsemidefinite programminggraph coloring

Mathematics Subject Classification ID

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

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

Cites work

• 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?)
• 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
• How false is Kempe's proof of the four color theorem? II
• 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

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)