Stars and Bonds in Crossing-Critical Graphs
| Authors | |
|---|---|
| Year of publication | 2008 |
| Type | Article in Periodical |
| Magazine / Source | Electronic Notes in Discrete Mathematics |
| MU Faculty or unit | |
| Citation | |
| Web | |
| Field | General mathematics |
| Keywords | crossing number; crossing-critical graph |
| Description | The structure of all known infinite families of crossing--critical graphs has led to the conjecture that crossing--critical graphs have bounded bandwidth. If true, this would imply that crossing--critical graphs have bounded degree, that is, that they cannot contain subdivisions of $K_{1,n}$ for arbitrarily large $n$. In this paper we prove two results that revolve around this conjecture. On the positive side, we show that crossing--critical graphs cannot contain subdivisions of $K_{2,n}$ for arbitrarily large $n$. On the negative side, we show that there are graphs with arbitrarily large maximum degree that are $2$-crossing--critical in the projective plane. |
| Related projects: |