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

1. Crossing number and edge addition

    1. Crossing number and edge addition


      Add remark

      Problem 1.1.

      [Jacob Fox] Is there a constant $c < 1$ such that any graph $G$ with $m$ edges and any two non-adjacent vertices $u,v$ in $G$ satisfy $\text{cr}(G + uv) \leq \text{cr}(G) + c \cdot m$?
          Note: 1. The same statement for $c = 1$ is known to be true. 2. The statement cannot be proven for $c < 1/8$ by considering $K_{3,3}$ minus and edge.

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