Ghosh et al.'s conjecture on even-length paths in planar graphs

For a finite simple graph GG, let N(G,H)N(G,H) be the number of unlabeled, not necessarily induced copies of HH in GG. Define

f(n,H)=max{N(G,H):V(G)=n and G is planar}.f(n,H)=\max\{N(G,H): |V(G)|=n \text{ and } G \text{ is planar}\}.

Let PkP_k denote the path on kk vertices, so P2+1P_{2\ell+1} has even length 22\ell. Ghosh et al.'s conjecture. For every fixed integer 2\ell\ge 2,

f(n,P2+1)=4(n)+1+O(n).f(n,P_{2\ell+1})=4\ell\left(\frac{n}{\ell}\right)^{\ell+1}+O(n^\ell).

The lower bound is supplied by blowing up one bipartition class of a cycle C2C_{2\ell}, while the conjectured matching upper bound remained to be proved in the source. The corresponding conjecture has since been resolved by Lv, Győri, He, Salia, Tompkins and Zhu.

Sources & referencesView supporting material

Primary source

Zhen Liu and Chuanshu Wu, “The maximum number of paths of even length in a planar graph”, arXiv:2607.27284 (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.