Odd-cycle-different Hamiltonian paths conjecture

For integers k>1k>1, let C2k+1C_{2k+1} denote the cycle of odd length 2k+12k+1. Two Hamiltonian paths on nn vertices are C2k+1C_{2k+1}-different if their union contains a subgraph isomorphic to C2k+1C_{2k+1}. Let the number of balanced bipartitions of an nn-element ground set be the corresponding extremal benchmark.

Odd-cycle-different Hamiltonian paths conjecture. If k>1k>1 and nn is large enough, the maximal number of pairwise C2k+1C_{2k+1}-different Hamiltonian paths on nn vertices is equal to the number of balanced bipartitions of the ground set nn.

This is proposed as a relaxed extension of the paper's theorem for triangles. The source presents it as open; it also gives supporting asymptotic results in some cases.

Sources & referencesView supporting material

Primary source

István Kovács and Dániel Soltész, “Triangle-different Hamiltonian paths”, arXiv:1608.05237 (2016).

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.