New infinite families of almost-planar crossing-critical graphs
| Authors | |
|---|---|
| Year of publication | 2008 |
| Type | Article in Periodical |
| Magazine / Source | Electronic Journal of Combinatorics |
| MU Faculty or unit | |
| Citation | |
| Web | online paper |
| Field | General mathematics |
| Keywords | crossing-critical; graph |
| Description | We show that, for all choices of integers $k>2$ and $m$, there are simple $3$-connected $k$-crossing-critical graphs containing more than $m$ vertices of each even degree $\leq2k-2$. This construction answers one half of a question raised by Bokal, while the other half asking analogously about vertices of odd degrees at least $7$ in crossing-critical graphs remains open. Furthermore, our newly constructed graphs have several other interesting properties; for instance, they are almost planar and their average degree can attain any rational value in the interval $\big[3+\frac15,6-\frac8{k+1}\big)$. |
| Related projects: |