Kao's conjecture on Hamiltonicity of Cartesian products with odd paths

From papers

Let GG be a graph with a {P2,P3}\{P_2,P_3\}-factor, meaning a spanning subgraph whose components are copies of P2P_2 or P3P_3, and let PnP_n be the path on nn vertices. Write Δ(G)\Delta(G) for the maximum degree of GG, and call GPnG\Box P_n balanced bipartite when its two bipartition classes have equal cardinality.

Kao's conjecture. If n4Δ(G)2n\geq 4\Delta(G)-2 and GPnG\Box P_n is balanced bipartite, then GPnG\Box P_n 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 P3PnP_3\Box P_n 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

No solutions have been posted yet.