Kao's conjecture on Hamiltonicity of Cartesian products with odd paths
Kao's conjecture on Hamiltonicity of Cartesian products with odd paths
Let be a graph with a -factor, meaning a spanning subgraph whose components are copies of or , and let be the path on vertices. Write for the maximum degree of , and call balanced bipartite when its two bipartition classes have equal cardinality.
Kao's conjecture. If and is balanced bipartite, then is hamiltonian.
This conjecture concerns Hamilton cycles in Cartesian products of graphs with paths. The surrounding results establish Hamiltonicity under related hypotheses, while the conjecture specifically addresses the odd-path case in which the standard construction using does not apply; its resolution is not given in the supplied text.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Irena Hrastnik Ladinek, Tjasa Paj Erker and Simon Spacapan, “Hamiltonicity of Cartesian products of trees with odd paths”, arXiv:2607.09270 (2026).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.