Abstract
In this paper we study alternating cycles in graphs embedded in a surface. We observe that 4-vertex-colorability of a triangulation on a surface can be expressed in terms of spanninq quadrangulations, and we establish connections between spanning quadrangulations and cycles in the dual graph which are noncontractible and alternating with respect to a perfect matching. We show that the dual graph of an Eulerian triangulation of an orientable surface other than the sphere has a perfect matching M and an M-alternating noncontractible cycle. As a consequence, every Eulerian triangulation of the torus has a nonbipartite spanning quadrangulation. For an Eulerian triangulation G of the projective plane the situation is different: If the dual graph G∗ is nonbipartite, then G∗ has no noncontractible alternating cycle, and all spanning quadrangulations of G are bipartite. If the dual graph G∗ is bipartite, then it has a noncontractible, M-alternating cycle for some (and hence any) perfect matching, G has a bipartite spanning quadrangulation and also a nonbipartite spanning quadrangulation.
| Original language | English |
|---|---|
| Journal | Universitaet Hamburg. Mathematisches Seminar. Abhandlungen |
| Volume | 87 |
| Issue number | 2 |
| Pages (from-to) | 357-368 |
| ISSN | 0025-5858 |
| DOIs | |
| Publication status | Published - 2017 |
Fingerprint
Dive into the research topics of 'Spanning quadrangulations of triangulated surfaces'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver