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

From papers

Let P1{\cal P}_1 denote the class of 1-planar graphs, and let ForbP1,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):GForbP1,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 n5n\geq 5,

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

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

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

Licheng Zhang, Yuanqiu Huang and Fengming Dong, “Extremal 1-planar graphs without k-cliques”, arXiv:2604.21589 (2026).

Solutions 0

No solutions have been posted yet.