| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

3. Crossing number and edge partition

    1. Crossing number and edge partition

          There is a known result: any graph $G$ can be decomposed as a union of two subgraphs $G = G_1 \cup G_2$ such that $\text{cr}(G_1) + \text{cr}(G_2) \leq \frac{3}{8}\text{cr}(G)$

      Add remark

      Problem 3.1.

      [Laszlo Szekely] Is there a constant $c < 3/8$ such that any graph $G$ can be decomposed as a union of two subgraphs $G = G_1 \cup G_2$ with $\text{cr}(G_1) + \text{cr}(G_2) \leq c\cdot\text{cr}(G)$?
          Note: $c = \frac{7}{24}$ is sufficient when $G$ is the complete graph.

      Reference: A. Owens. On the biplanar crossing number. IEEE Transactions on Circuit Theory 18 (1971): 277–280.

      E. Czabarka, O. Sykora, L. A. Szekely, I. Vrto. Biplanar crossing numbers I: a survey of problems and results. More Sets, Graphs and Numbers, Eds. E. Gyori et al., Bolyai Society Mathematical Studies 15 2006, 57–77.

      J. Pach, L.A. Szekely, Cs.D. Toth, G. Toth. Note on k-planar crossing numbers. Computational Geometry: Theory and Applications 68 (2018): 2–6.

      J. Asplund, G. Clark, G. Cochran, E. Czabarka, A. Hamm, G. Spencer, L. Szekely, L. Taylor, Z. Wang. Using block designs in crossing number bounds. Journal of Combinatorial Designs 27(10) (2019): 586–597.

          Cite this as: AimPL: Albertson conjecture and related problems, available at http://aimpl.org/albertson.