← All problems

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

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 G□PnG\Box P_n balanced bipartite when its two bipartition classes have equal cardinality.

Kao's conjecture. If n≥4Δ(G)−2n\geq 4\Delta(G)-2 and G□PnG\Box P_n is balanced bipartite, then G□PnG\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 P3□PnP_3\Box P_n does not apply; its resolution is not given in the supplied text.

References
  1. Irena Hrastnik Ladinek, Tjasa Paj Erker and Simon Spacapan, “Hamiltonicity of Cartesian products of trees with odd paths”, arXiv:2607.09270 (2026).

Progress summary

Never refreshed

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.