Extremal 1-planar graphs without k-cliques

Abstract

In 2016, Dowden initiated the study of planar Turán-type problems, which has since attracted considerable attention. Recently, Bekos et al. proved that every $K_3$-free $1$-planar graph on $n\ge 4$ vertices has at most $3n-6$ edges. In this paper, we strengthen this bound to $3n-8$, which is tight for all even $n\ge 8$. Furthermore, we show that every $K_4$-free $1$-planar graph on $n\ge 3$ vertices has at most $\lfloor \frac{7n}{2}\rfloor -7$ edges, and this bound is tight for all integers $n\ge 9$. We also prove that every $K_5$-free $1$-planar graph on $n\ge 3$ vertices has at most $4n-8$ edges, which is tight for $n=8$ and for all integers $n\ge 10$.

24 pages, 15 figures