Graph coloring and semidefinite rank

DOI10.1007/978-3-031-06901-7_29zbMath1497.90143arXiv2202.10515OpenAlexW4285128174MaRDI QIDQ2164723

David P. Williamson, Renee Mirka, Devin Smedira

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

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

Cites Work

• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• The sandwich theorem
• The four-colour theorem
• Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
• Algebraic characterization of uniquely vertex colorable graphs
• Approximate graph coloring by semidefinite programming
• On the Shannon capacity of a graph
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Graph colouring and the probabilistic method
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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