Optimal-colouring conjecture for fixed-length de Bruijn cycle decompositions
Optimal-colouring conjecture for fixed-length de Bruijn cycle decompositions
Let denote the maximum number of eBugs in an -valid colouring with colours and LEDs per eBug. An optimal colouring is one attaining the upper bound ; necessarily . Optimal-colouring conjecture.
whenever divides and . This characterises when optimal colourings exist and would resolve the exact determination problem in these divisibility cases; the conjecture was confirmed computationally for all with , and is known for by Bryant's decomposition result.
Sources & referencesView supporting material
Primary source
Tony Grubman, Y. Ahmet Şekercioğlu and David R. Wood, “Partitioning de Bruijn Graphs into Fixed-Length Cycles for Robot Identification and Tracking”, arXiv:1502.02199 (2016).
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.