Crosing-critical graphs have bounded tree-width and path-width

• James F. Geelen, R. Bruce Richter, Gelasio Salazar: Embedding grids in surfaces. Eur. J. Comb. 25(6): 785-792 (2004)

We show that if a very large grid is embedded in a surface, then a large subgrid is embedded in a disc in the surface. This readily implies that: (a) a minor-minimal graph that does not embed in a given surface has no very large grid; and (b) a minor-minimal k-representative embedding in the surface has no very large grid. Similar arguments show (c) that if G is minimal with respect to crossing number, then G has no very large grid.

•  Petr Hlinený: Crossing-number critical graphs have bounded path-width. J. Comb. Theory, Ser. B 88(2): 347-367 (2003)

No large K_2,m subdivision

• Petr Hlinený, Gelasio Salazar: Stars and bonds in crossing-critical graphs. Journal of Graph Theory 65(3): 198-215 (2010)

Interesting construction in the projective plane

Crossing-critical graphs with large maximum degree

•  Zdenek Dvorak, Bojan Mohar: Crossing-critical graphs with large maximum degree. J. Comb. Theory, Ser. B 100(4): 413-417 (2010)

Theorem 6. For every k>=171 and every d, there exists a k-crossing-critical graph H containing a vertex of degree at least d.

     

Conjecture 7. For every positive integer k there exists an integer D = D(k) such that every k-crossing-critical graph contains at most k vertices whose degree is larger than D.

It is not even obvious that there exist k-crossing-critical graphs with arbitrarily many vertices of degree more than 6. Surprisingly, such examples have been constructed recently by Hlinˇený [4]. His examples may contain arbitrarily many vertices of any even degree smaller than 2k −1. Let us also remark that the use of Lemma 4 means that we do not present an explicit counterexample to Conjecture 1, but only its supergraph. Consequently, we cannot ensure that the counterexample has some particular properties, e.g., we cannot prove that Conjecture 1 fails for 3-connected simple graphs. It might be of interest to rectify this problem by carrying out the construction explicitly, replacing the cycles of thick edges by some suitable planar graphs.