The Kuratowski-edge conjecture for crossing-critical graphs

Let GG be a graph. An edge of GG is a Kuratowski edge if it belongs to a subgraph homeomorphic to K3,3K_{3,3} or K5K_5. Kuratowski-edge conjecture. If every edge of GG is a Kuratowski edge, then GG can be made crossing-critical by a suitable multiplication of its edges.

The conjecture proposes a structural sufficient condition for a graph to admit an edge multiplication that makes it crossing-critical. The paper establishes positive results for a large family of graphs and for individual Kuratowski edges, but notes that a full characterization of the relevant class remains open.

Sources & referencesView supporting material

Primary source

Laurent Beaudou, César Hernández-Vélez and Gelasio Salazar, “Making a graph crossing-critical by multiplying its edges”, arXiv:1112.3167 (2011).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.