Page 43 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 43
k Ellingham: Construction Techniques for Graph Embeddings 31
• Map local orientation of triangles in Ψ to new triangulation: use same orientation for
primary triangles, reverse for secondary triangles. Consistent if and only if original
orientation consistent.
Other important results by Bouchet and coauthors
Theorem: If Ψ is a triangulation of an eulerian complete multipartite graph then G(m) has
a triangulation of the same orientability as Ψ, obtained using a generative m -valuation,
for all m ≥ 2. Proof shows that we can avoid odd order components of diagonal graph
when m is even.
Theorem: If p is an odd prime and Ψ is a triangulation of a graph G such that Ψ∗ (the
dual of Ψ) has a nowhere zero p -flow then there is a triangular embedding of G(p) of the
same orientability as Ψ.
Note: Since all 2-connected graphs have nowhere zero 6-flows (Seymour), can always do
this for p ≥ 7. If 5-flow conjecture is true, would always work for p = 5, too. In special
cases can work for p = 3 or 5 (e.g., see below).
Theorem: If Ψ is a triangulation of a 4-colourable graph G =∼ K4, then we get a triangular
embedding of G(m) of the same orientability as Ψ for m = 3 and hence (by repetition, and
using the fact that a 4-face-colourable graph has a nowhere zero 4-flow) for all odd m .
Non-triangular embeddings
Bouchet’s constructions are for triangulations. But can use, perhaps in modified form,
if convert other embeddings into triangulations by adding extra edges or vertices. A
couple of examples:
1. Lifting embeddings where all faces have even lengths, paper by Bouchet. First add
a new vertex inside each face so we have an Eulerian triangulation. Now find an m -
valuation φ so that values/coefficients of φ are generators of m for original vertices,
but are 0 for new vertices.
2. In some cases it makes sense to just directly apply Bouchet’s results after convert-
ing to a triangulation. For example, Ellingham and Schroeder [ES12] used Bouchet’s
results to help construct hamilton cycle embeddings of regular complete tripartite
graphs:
hamilton cycle embedding of Kt ,t ,t
→ triangulation of K2t ,t ,t ,t (add vertex in each face)
and apply Bouchet lifting to get
triangulation of K2m t ,m t ,m t ,m t
• Map local orientation of triangles in Ψ to new triangulation: use same orientation for
primary triangles, reverse for secondary triangles. Consistent if and only if original
orientation consistent.
Other important results by Bouchet and coauthors
Theorem: If Ψ is a triangulation of an eulerian complete multipartite graph then G(m) has
a triangulation of the same orientability as Ψ, obtained using a generative m -valuation,
for all m ≥ 2. Proof shows that we can avoid odd order components of diagonal graph
when m is even.
Theorem: If p is an odd prime and Ψ is a triangulation of a graph G such that Ψ∗ (the
dual of Ψ) has a nowhere zero p -flow then there is a triangular embedding of G(p) of the
same orientability as Ψ.
Note: Since all 2-connected graphs have nowhere zero 6-flows (Seymour), can always do
this for p ≥ 7. If 5-flow conjecture is true, would always work for p = 5, too. In special
cases can work for p = 3 or 5 (e.g., see below).
Theorem: If Ψ is a triangulation of a 4-colourable graph G =∼ K4, then we get a triangular
embedding of G(m) of the same orientability as Ψ for m = 3 and hence (by repetition, and
using the fact that a 4-face-colourable graph has a nowhere zero 4-flow) for all odd m .
Non-triangular embeddings
Bouchet’s constructions are for triangulations. But can use, perhaps in modified form,
if convert other embeddings into triangulations by adding extra edges or vertices. A
couple of examples:
1. Lifting embeddings where all faces have even lengths, paper by Bouchet. First add
a new vertex inside each face so we have an Eulerian triangulation. Now find an m -
valuation φ so that values/coefficients of φ are generators of m for original vertices,
but are 0 for new vertices.
2. In some cases it makes sense to just directly apply Bouchet’s results after convert-
ing to a triangulation. For example, Ellingham and Schroeder [ES12] used Bouchet’s
results to help construct hamilton cycle embeddings of regular complete tripartite
graphs:
hamilton cycle embedding of Kt ,t ,t
→ triangulation of K2t ,t ,t ,t (add vertex in each face)
and apply Bouchet lifting to get
triangulation of K2m t ,m t ,m t ,m t
