Characterizing all graphs with 2-exceptional edges
Drago Bokal, Jesús Leaños · Ars Mathematica Contemporanea · 2018
Dirac and Shuster in 1954 exhibited a simple proof of Kuratowski theorem by showing that any 1 -crossing-critical edge of G belongs to a Kuratowski subdivision of G . In 1983, Širáň extended this result to any 2 -crossing-critical edge e with endvertices b and c of a graph G with crossing number at least two, whenever no two blocks of G − b − c contain all its vertices. Calling an edge f of G k - exceptional whenever f is k -crossing-critical and it does not belong to any Kuratowski subgraph of G , he showed that simple 3 -connected graphs with k -exceptional edges exist for any k ≥ 6 , and they exist even for arbitrarily large difference of c r ( G ) − c r ( G − f ) . In 1991, Kochol constructed such examples for any k ≥ 4 , and commented that Širáň’s result holds for any simple graph. Examining the case when two blocks contain all the vertices of G − b − c , we show that graphs with k -exceptional edges exist for any k ≥ 2 , albeit not necessarily simple. We confirm that no such simple graphs with 2 -exceptional edges exist by applying the techniques of the recent characterization of 2 -crossing-critical graphs to explicitly describe the set of all graphs with 2 -exceptional edges and noting they all contain parallel edges. In this context, the paper can be read as an accessible prelude to the characterization of 2 -crossing-critical graphs.