Linear circumference conjecture for random cubic planar multigraphs
Let be a graph chosen uniformly at random from the class of all cubic planar multigraphs on vertex set . Its circumference is the length of its longest cycle.
Linear circumference conjecture.
Random cubic planar multigraphs cannot have Hamiltonian cycles because linearly many vertices have an attached loop, but the conjecture asserts that they nevertheless have cycles of linear length with high probability. This would determine the asymptotic order of the circumference and is used to obtain the corresponding weakly supercritical result for random planar graphs.
References
Primary source
Mihyun Kang and Michael Missethan, “Longest and shortest cycles in random planar graphs”, arXiv:2006.09697 (2021).
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
No solutions have been posted yet.