The extremal edge-count conjecture for odd-order triangle-free 1-planar graphs

Let P1{\cal P}_1 denote the class of 1-planar graphs, and let Forb⁡P1,n(K3)\operatorname{Forb}_{{\cal P}_1,n}(K_3) be the set of nn-vertex 1-planar graphs containing no copy of K3K_3. Write

exP1,n(K3)=max⁡{e(G):G∈Forb⁡P1,n(K3)}.ex_{{\cal P}_1,n}(K_3)=\max\{e(G):G\in\operatorname{Forb}_{{\cal P}_1,n}(K_3)\}.

Extremal edge-count conjecture. For any odd n≥5n\geq 5,

exP1,n(K3)=3n−9.ex_{{\cal P}_1,n}(K_3)=3n-9.

The theorem preceding this conjecture establishes the upper bound exP1,n(K3)≤3n−8ex_{{\cal P}_1,n}(K_3)\leq 3n-8 for n≥8n\geq 8, with equality for even nn. For odd n≥9n\geq 9, it is unknown whether the upper bound can be attained; the conjecture asserts that the exact extremal value is instead 3n−93n-9. Karpov constructed bipartite examples with 3n−93n-9 edges for every odd n≥5n\geq 5.

References

Primary source

Licheng Zhang, Yuanqiu Huang and Fengming Dong, “Extremal 1-planar graphs without k-cliques”, arXiv:2604.21589 (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.