Depts for Mathematics at the Univ of Szeged - Czabarka Éva: A quantitative Kuratowski theorem

Czabarka Éva: A quantitative Kuratowski theorem

$Download as iCal file$

$Export Event$ Export Event

Preserve formatting in description (only supported in some calendar applications)

Tuesday, 21. May 2024, 10:50 - 11:40

Kuratowski's theorem states that a graph is non-planar precisely when it contains a topological

K_{5}

$K_5$ or a topological

K_{3, 3}

$K_{3,3}$ (i.e., a subdivision of a

K_{3}

$K_3$ or a

K_{3, 3}

$K_{3,3}$ ).
Accordingly, we call a subgraph

X

$X$ of

G

$G$ cross-inducing, if

X

$X$ is a topological

K_{5}

$K_5$ or
a topological

K_{3, 3}

$K_{3,3}$ .
A graph with crossing number 1 may contain arbitrary many cross-inducing subgraphs (e.g., replace an edge of a

K_{5}

$K_5$ with arbitrary many internally disjoint paths).
We define the (possibly infinite valued) function

f (k)

$f(k)$ as the supremum of the crossing numbers of graphs with exactly

k

$k$ cross-inducing subgraphs (this supremum is a
maximum when

f (k)

$f(k)$ is finite).
It is clear that

f (k) i s i n c r e a s i n g a n d

$f(k) is increasing and$ k\le f(k)

. (e . g . t a k e

$. (e.g. take$ k

d i s j o i n t

$disjoint$ K_5

$'s). We show that$ f(k)=k

$for$ k\le 2

$and$ f(k)

$is finite for all$ k$.
This is joint work with Alec Helm and Géza Tóth.