The DDS optimality conjecture for book crossing numbers of complete graphs
The DDS optimality conjecture for book crossing numbers of complete graphs
Let be the complete graph on vertices, let denote its minimum number of crossings in a -page book drawing, and let denote the number of crossings in the DDS construction of in pages. DDS optimality conjecture. For all positive integers and ,
The conjecture asserts the optimality of the DDS construction for every number of pages and every complete graph. The paper presents this as a general conjecture; its case is supported by computations for all 8 values of considered there.
Sources & referencesView supporting material
Primary source
Etienne de Klerk, Dmitrii V. Pasechnik and Gelasio Salazar, “Improved lower bounds on book crossing numbers of complete graphs”, arXiv:1207.5701 (2012).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.