# Wydawnictwa / Czasopisma IMPAN / Colloquium Mathematicum / Wszystkie zeszyty

## $\ell ^{2}$-homology and planar graphs

### Tom 131 / 2013

Colloquium Mathematicum 131 (2013), 129-139 MSC: 05C10, 57M15. DOI: 10.4064/cm131-1-11

#### Streszczenie

In his 1930 paper, Kuratowski proves that a finite graph $\varGamma$ is planar if and only if it does not contain a subgraph that is homeomorphic to $K_5$, the complete graph on five vertices, or $K_{3,3}$, the complete bipartite graph on six vertices. This result is also attributed to Pontryagin. In this paper we present an $\ell ^2$-homological method for detecting non-planar graphs. More specifically, we view a graph $\varGamma$ as the nerve of a related Coxeter system and construct the associated Davis complex, $\varSigma _\varGamma$. We then use a result of the author regarding the (reduced) $\ell ^2$-homology of Coxeter groups to prove that if $\varGamma$ is planar, then the orbihedral Euler characteristic of $\varSigma _\varGamma /W_\varGamma$ is non-positive. This method not only implies as subcases the classical inequalities relating the number of vertices $V$ and edges $E$ of a planar graph (that is, $E\leq 3V-6$ or $E\leq 2V-4$ for triangle-free graphs), but it is stronger in that it detects non-planar graphs in instances the classical inequalities do not.

#### Autorzy

• Timothy A. SchroederDepartment of Mathematics and Statistics
Murray State University
Murray, KY 42071, U.S.A.
e-mail

## Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Odśwież obrazek