Graph coloring and semidefinite rank

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

David P. Williamson, Renee Mirka, Devin Smedira

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)

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
• Title not available (Why is that?)
• 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)