Working Seminar on Formal Models, Discrete Structures, and Algorithms

Degree-universal crossing-critical families of graphs

Mojca Bračič

When: December 4, 1pm

Where: room G2.91b


A k-crossing-critical graph G is a graph that has crossing number at least k∈N, and by removing any edge e∈G the crossing number decreases below k. For a set D⊆N, we say that the family of graphs F is D-universal, if and only if, for every assignment of integers {m_d|d∈D}, there exists a graph G∈F, such that G has at least m_d vertices of degree d for each d∈D. We say that a family of graphs is D-max-universal if D is inclusion-maximal with this property. We present a three parametric family of graphs G(l,n,m), where l,n,m are integers, such that l≥1, n≥3, m is odd, and m > 1. The graph G(l,n,m) is k-crossing-critical for m≥4k-1 and the family of this graphs is {3,4,2l+1}- max-universal. We also construct D-max-universal families of simple, 3-connected, k-crossing-critical graphs, for any D⊆N1-{1,2} with {3,4}⊆D or both 4∈D and D contains only even numbers, and any sufficiently large k.

This is joint work with Drago Bokal, Marek Derňár and Petr Hliněný.