The crossing number of the complete 4-partite graph \(K_{1,1,m,n}\)

• Published in: arXiv.org 2022-01
• Main Authors: Yang, Xiwu, Ni, Lu, Chen, Xiaodong, Yang, Yuansheng
• Format: Article
• Language: English
• Subjects: Lower bounds
• ISSN: 2331-8422

Let \(\textrm{cr}(G)\) denote the crossing number of a graph \(G\). The well-known Zarankiewicz's conjecture (ZC) asserted \(\textrm{cr}(K_{m,n})\) in 1954. In 1971, Harborth gave a conjecture (HC) on \(\textrm{cr}(K_{x_1,...,x_n})\). HC on \(K_{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 \(m\) and \(n\) are even, then \[\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 \(m\) and \(n\) are odd, then \[\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 \(m\) is even and \(n\) 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 \(m\) and \(n\) are even and ZC is true, then HC on \(K_{1,1,m,n}\) holds; if at least one of \(m\) and \(n\) is odd and both ZC and HC on \(K_{2,m,n}\) are true, then HC on \(K_{1,1,m,n}\) holds.