Problems in Topological Graph Theory

---

Go to the Table of Contents

---

Compiled by Dan Archdeacon

List Started: August 1995
Converted to the web: September 1998
Extensive revisions: December 2003

E-Mail:

dan.archdeacon@uvm.edu

Postal Mail:

Dan Archdeacon
Dept. of Math. and Stat.
University of Vermont
Burlington VT 05401-1455 USA

---

Abstract

Do you think you've got problems? I know I do. This paper contains an ongoing list of open questions in topological graph theory. If you are interested in adding a problem to this list please contact me at the addresses above. The spirit is inclusive---don't submit a problem you're saving for your graduate student. If it appears here, it's fair game. If you solve one of the problems, know some additional history, recognize it as phrased incorrectly, or think it’s just a stupid question, please let me know so that I can keep the list up-to-date. I've taken quite a bit of liberty editing the submissions. I apologize for any errors introduced. My original goal was to update the list monthly, however, that has proven too difficult. There is no guarantee that references are up-to-date.

Enjoy my problems---I do!

---

Table of Contents

• Classical questions on genus
• Obstructions to embeddings
• Paths, cycles, and matchings
• Coloring graphs and maps
• List colorings and choosability
• Flows
• Locally planar embeddings
• Crossing numbers
• Drawings
• Representing graphs and embeddings
• Geometric graphs
• Symmetries
• Random topological graph theory
• Book embeddings
• Other problems on planar graphs
• Miscellaneous problems
• Solved problems from previous editions
• Problems under construction

Return to the Main Table of Contents

---

The Problems

Classical questions on genus

• The effect of edge deletion on the nonorientable genus
• Rotations determined by edge orderings
• Nearly triangular imbeddings of complete graphs
• The genus of the complete graph minus a Hamiltonian cycle
• Quadrilateral embeddings of composition graphs
• Graphs that quadrangulate both the torus and Klein bottle
• The maximum genus of a signature on the complete graph
• The maximum genus of a simple bipartite graph
• The genus sequence of a signed graph

Return to the Main Table of Contents

Obstruction to embeddings

• Minor-minimal non-toroidal graphs
• Obstructions for the spindle surface
• Obsttructions for embedding digraphs
• Kuratowski covers

Return to the Main Table of Contents

Paths, cycles, and matchings

• The cycle double cover conjecture
• Sabidusi's compatibility conjecture
• (8,4)-directed-cycle covers
• Barnette's conjecture
• Hamilton cycles in toroidal graphs
• Double covering edges by perfect matchings
• Covering cubic graphs with perfect matchings
• Perfect matchings in cubic graphs that have empty intersection
• 2-Connected spanning subgraphs of bounded degree

Return to the Main Table of Contents

Coloring graphs and maps

• The earth-moon coloring problem
• Three edge-coloring orientable triangulations
• Uniquely colorable polyhedra
• Determining triangulations by their four-colorings
• Ringel's one-chromatic number of surfaces
• The d-diagonal chromatic number
• Coloring directed planar graphs
• Acyclic list-coloring planar graphs
• The linear arboricity of planar graphs
• 2-coloring plane triangulations
• Extending colorings of planar graphs
• Four-coloring all but three vertices of a toroidal graph
• Vertices of odd degree in a triangulation
• When are there local colorings?
• Edge coloring the n-cube

Return to the Main Table of Contents

List colorings and choosability

• List edge-colorings
• (a:b)-Choosability
• Defective list colorings
• Defective list colorings of planar graphs
• Extending list-5-colorings of planar graphs
• 3-choosability of planar graphs

Return to the Main Table of Contents

Flows

• Tutte's nowhere-zero 3- 4- and 5-flow conjectures
• (2 + epsilon)-flows
• Bouchet's 6-flow conjecture
• Realizing degree sequences with graphs having 3-flows

Return to the Main Table of Contents

Locally planar embeddings

• Planar graphs in nonplanar surfaces
• Orientable genus of graphs of bounded nonorientable genus
• Finding separating cycles in embedded graphs
• Interpolation conjectures on separating cycles in embedded graphs
• Spanning trees with small degree
• Finding embeddings of large face width
• LEW embeddings of weighted graphs

Return to the Main Table of Contents

Crossing numbers

• The crossing number of the complete graph
• A combinatorial generalization of drawing the complete graph
• Turan's brickyard problem: the crossing number of K(n,m)
• The crossing number of the cube
• The crossing number of a product of cycles
• The crossing number of dense graphs
• How often must curves touch?
• A crossing number hereditary under minors
• Alternate definitions of the crossing number
• Trading handles for crossings

Return to the Main Table of Contents

Drawings

• The thrackle conjecture
• Is the maximum crossing number hereditary?
• Straight-ahead cycles in drawings of Eulerian graphs
• Two problems about drawing graphs in the plane
• Four questions about drawing the complete graph
• Drawing chords in a disk
• Drawing rotations in the plane

Return to the Main Table of Contents

Representating graphs and embeddings

• Planar graphs with integer length straight edges
• Representing graphs by intersecting line segments
• Representing graphs by spheres in 3-space
• Recognizing and coloring rectangle visibility graphs

Return to the Main Table of Contents

Geometric graphs

• The chromatic number of the plane and of space
• The rectilinear crossing number
• The geometric thickness of a graph
• Paths in complete geometric graphs
• Rooted geometric forests with fixed point-sets
• Finding geometric trees with fixed bipartite point-sets
• Geometric graphs with each edge crossing at most three others
• Geometric graphs without three disjoint edges
• Geometric realizations of n-vertex graphs

Return to the Main Table of Contents

Symmetries

• Planar coverings: the 1-2-infinity conjecture
• Regular maps on nonorientable surfaces
• Automorphism groups of Cayley maps
• Automorphisms adjacent to the identity

Return to the Main Table of Contents

Random topological graph theory

• The expected number of regions in a random embedding of the complete graph
• The average genus of the random graph
• Partitioning into complete graphs

Return to the Main Table of Contents

Book embeddings

• The pagenumber of complete bipartite graphs
• The average pagenumber of a permutation

Return to the Main Table of Contents

Other problems on planar graphs

• Packing trees into planar graphs
• Tree-tree triangulations
• Outerplanar partitions of planar graphs
• Cuts in digraphs and Woodall's conjecture
• Combinatorial curvature
• Iterated clique graphs of triangulations
• Boundary-preserving maps between disks
• Which coronas are simple?

Return to the Main Table of Contents

Miscellaneous problems

• Colin de Verdiere's mu parameter
• Unacoidable apex-forest and outer-planar graphs
• Graphs with a K_5 subdivision
• Complete graphs in line graphs
• Faces covering the edges of a graph
• Dimension and outer-planar graphs
• Two-dimensional Catalan numbers
• Antichains in the cycle-continuous order
• Mapping planar graphs onto cycles
• The approximability of graph minimum genus embeddings

Return to the Main Table of Contents

Solved problems from previous editions

• Toroidal triangulations with flat faces
• The genus of the complete tripartite graph
• Finding the genus of a cubic graph
• Planar graphs in nonplanar surfaces
• An unusual way to draw graphs in books
• Regular Cayley maps that are neither balanced nor antibalanced

Return to the Main Table of Contents

Under construction (material on these pages may not be up-to-date)

• Longest paths in polyhedral graphs
• Generalizations of Tait coloring cubic graphs

Return to the Main Table of Contents

---

The End

---