|
|
|
|||||||
| Év szerint | Hónap szerint | Ugrás a hónaphoz | |||||||
Czabarka Éva: A quantitative Kuratowski theorem |
|
|||
|
|
||||
|
||||
| Kuratowski's theorem states that a graph is non-planar precisely when it contains a topological $K_5$ or a topological $K_{3,3}$ (i.e., a subdivision of a $K_3$ or a $K_{3,3}$). Accordingly, we call a subgraph $X$ of $G$ cross-inducing, if $X$ is a topological $K_5$ or a topological $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$ with arbitrary many internally disjoint paths). We define the (possibly infinite valued) function $f(k)$ as the supremum of the crossing numbers of graphs with exactly $k$ cross-inducing subgraphs (this supremum is a maximum when $f(k)$ is finite). It is clear that $f(k) is increasing and $k\le f(k)$. (e.g. take $k$ 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. |
||||
Esemény exportálása JEvents v3.1.8 Stable Copyright © 2006-2013