The two-Kuratowski-edge conjecture for simultaneous crossing-criticality

Let GG be a graph, and let ee and ff be Kuratowski edges of GG, meaning that each belongs to a subgraph homeomorphic to K3,3K_{3,3} or K5K_5. A graph obtained by multiplying edges of GG is formed by adding parallel edges to edges of GG. Two-Kuratowski-edge conjecture. There exists a graph HH, obtained by multiplying edges of GG, such that both ee and ff are crossing-critical in HH.

This is presented as the immediate next step toward the Kuratowski-edge conjecture. The paper proves that a single Kuratowski edge can be made crossing-critical, while simultaneous crossing-criticality for two such edges is stated as difficult and 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.