The crossing number of the complete 4-partite graph K1,1,m,nK_{1,1,m,n}

preprint2022arXivOpen access

Abstract

Let cr(G)\textrm{cr}(G) denote the crossing number of a graph GG. The well-known Zarankiewicz's conjecture (ZC) asserted cr(Km,n)\textrm{cr}(K_{m,n}) in 1954. In 1971, Harborth gave a conjecture (HC) on cr(Kx1,...,xn)\textrm{cr}(K_{x_1,...,x_n}). HC on K1,m,nK_{1,m,n} is verified if ZC is true by Ho et al. in 2021. In this paper, we showed the following results: If both mm and nn are even, then cr(K1,1,m,n)≥12(cr(Km+1,n+3)+cr(Km+3,n+1)−mn−14(m2+n2));\textrm{cr}(K_{1,1,m,n})\geq \frac{1}{2}(\textrm{cr}(K_{m+1,n+3})+\textrm{cr}(K_{m+3,n+1})-mn-\frac{1}{4}(m^2+n^2)); If both mm and nn are odd, then cr(K1,1,m,n)≥12(cr(K1,m+1,n+1)+cr(K2,m,n)−14(m+1)(n+1)+1);\textrm{cr}(K_{1,1,m,n})\geq \frac{1}{2}(\textrm{cr}(K_{1,m+1,n+1})+\textrm{cr}(K_{2,m,n})-\frac{1}{4}(m+1)(n+1)+1); If mm is even and nn is odd, then \begin{equation}\nonumber \begin{split} \textrm{cr}(K_{1,1,m,n})&\geq \frac{1}{4}(\textrm{cr}(K_{m+1,n+2})+\textrm{cr}(K_{m+3,n+2})+2\textrm{cr}(K_{2,m,n}) \\&-m(n+1)-\frac{1}{4}(n+1)^2). \end{split} \end{equation} The lower bounds in our result imply that if both mm and nn are even and ZC is true, then HC on K1,1,m,nK_{1,1,m,n} holds; if at least one of mm and nn is odd and both ZC and HC on K2,m,nK_{2,m,n} are true, then HC on K1,1,m,nK_{1,1,m,n} holds.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.