Problems from the book Graphs on Surfaces

by B. Mohar and C. Thomassen

This page contains the list of open problems and conjectures presented in Mohar and Thomassen's book on Graphs on Surfaces. It also contains information on any progress made towards their solution.

Statements bear the same numbers as in the book

Chapter 2

If true, the following conjecture of Thomassen [Th81] is a planarity criterion for a special class of graphs that involves only K5.

Conjecture 2.5.7. Let G be a 4-connected graph with n vertices and at least 3n-6 edges. Then G is planar if and only if G contains no subdivision of K5.

Recall that a planar graph on n vertices contains at most 3n-6 edges. Having that many edges, it is a triangulation and thus 3-connected. 

We were informed by Wolfgang Mader that Conjecture 2.5.7 follows from his characterization of graphs on n vertices with 3n-6 edges not containing a subdivision of K5 [3]. This result is also quoted as Theorem 8.3.9. in Diestelīs book [2].

P. D. Seymour (private communication, 1983) made the following conjecture:

Conjecture 2.5.8. A 5-connected graph is planar if and only if it does not contain a subdivision of K5.

Note that Conjecture 2.5.8 becomes false if we replace "5-connected" by "4-connected" because of K4,4. It can be shown that each of Conjectures 2.5.7 and 2.5.8 implies the following theorem which was conjectured by Dirac [Di64] and proved recently by Mader [Ma98 ,Ma99].

Mader's Theorem. Any graph with n vertices and at least 3n-5 edges contains a subdivision of K5.

H. Harborth (private communication) has raised the following

Problem 2.8.15. Does every planar graph have a straight line representation such that all edges have integer length?

Brightwell and Scheinerman [BS93] showed that this cannot in general be achieved by a circle packing representation since otherwise it would be possible to trisect an angle of π/3 by ruler and compass.

Chapter 4

Theorem 4.3.2 (Thomassen [Th90b]). There is a polynomially bounded algorithm which, for a given Π-embedded graph G, finds a shortest Π-noncontractible cycle, a shortest Π-nonseparating cycle, and a shortest Π-onesided cycle of G whenever such a cycle exists.

More generally, the fundamental cycle method applies to an arbitrary family C of cycles of a graph with the property that the cycles not in C generate a subspace of the cycle space that contains no cycle from C. In other words, we can find, in polynomial time, a shortest cycle outside a given subspace of the cycle space whenever the membership in that subspace can be tested in polynomial time. In contrast, to find a shortest cycle in a given subspace of the cycle space is not that easy. For example, the following problems are unsolved:

Problem 4.3.3. (a) Is there a polynomially bounded algorithm that finds a shortest Π-contractible cycle of a Π-embedded graph G?
     (b) Is there a polynomially bounded algorithm that finds a shortest surface separating cycle of a Π-embedded graph G?
     (c) Is there a polynomially bounded algorithm that finds a shortest Π-twosided cycle of a Π-embedded graph G?

Problem 4.3.3 (a) was raised by Thomassen [Th90b] who pointed out that the answer is simple if there are no vertices of degree less than three: We may assume that G is 2-connected. If one of the cycles of length at most 5 is Π-contractible, then a shortest Π-contractible cycle of G is within this set. Otherwise, a shortest Π-contractible cycle is one of the Π-facial cycles. This yields an answer in polynomial time.

Up until 2009, Problem 4.3.3 has been solved. The subquestion (c) turned out to have an easy answer, see HERE for explanation. An answer for questions 4.3.3(a) and (b) is provided in
[S. Cabello, Finding shortest contractible and shortest separating cycles in embedded graphs, SODA'09]. From the abstract of that paper: "We give a polynomial-time algorithm to find a shortest contractible cycle (i.e. a closed walk without repeated vertices) in a graph embedded in a surface. In contrast, we show that finding a shortest contractible cycle through a given vertex is NP-hard. We also show that finding a shortest [surface] separating cycle in an embedded graph is NP-hard."

The genus problem is hard even for small graphs. Let K3,3,3,3 denote the complete four-partite graph (obtained from K12 by removing the edges of four disjoint 3-cycles).

Problem. Prove that g(K3,3,3,3) > 4.

This problem is equivalent to the statement that K3,3,3,3 does not triangulate the orientable surface of genus 4. White proved in the second edition of his book [Wh73, Example 3, p. 169] that g(K3,3,3,3) is at most 5. Jungerman [Ju75] reports that the genus of this graph is at least 5, but his conclusion has only been derived by computer. Hence, the above problem is not to verify the conclusion but to present a selfcontained proof.

Problem 4.4.10*. Does there exist a number c, 0 < c < 1, such that every graph with n vertices, whose minimum degree is at least cn and whose number of edges is divisible by 3, triangulates an orientable surface?

* In the above problem, the authors have overlooked the parity condition. For orientable surfaces the number of edges should have the same parity as n. Below are the modified problems A and B.

Problem 4.4.10A. Does there exist a number c, 0 < c < 1, such that every graph with n vertices, whose minimum degree is at least cn and whose number of edges is divisible by 3 and has the same parity as n, triangulates an orientable surface?

Problem 4.4.10B. Does there exist a number c, 0 < c < 1, such that every graph with n vertices, whose minimum degree is at least cn and whose number of edges is divisible by 3, triangulates a nonorientable surface?

Chapter 5

A function w: E(G) –> R+ such that w(Q) < w(C) for every Π-facial walk Q and every Π-noncontractible cycle C is called an LEW-weight function.

Problem 5.1.10. Do there exist polynomially bounded algorithms for the following problems:
     (a) Given is a graph G embedded in a surface S. Does G have an LEW-weight function?
     (b) Does a given graph G have an embedding which admits an LEW-weight function?

An embedding of a 2-connected graph has face-width 2 or more if and only if all facial walks are cycles. Therefore the existence of embeddings of face-width at least 2 is related to the Cycle Double Cover Conjecture (Szekeres [Sz73], Seymour [Se79]) which says that every 2-connected graph contains cycles C1, ..., Cq such that each edge of G is contained in precisely two of the cycles. Maybe even the following stronger conjectures hold.

Conjecture 5.5.15 (Haggard [Ha77]). Every 2-connected graph has an embedding of face-width 2 or more.

Archdeacon [Ar84] proved Conjecture 5.5.15 for 4-connected graphs.

Conjecture 5.5.16 (Jaeger [Ja85]). Every 2-connected graph has an orientable embedding of face-width 2 or more.

We refer to Jaeger [Ja85] and Zhang [Zh96] for further information on the Cycle Double Cover Conjecture. To prove the Cycle Double Cover Conjecture, it suffices to show that every 3-connected cubic graph which is not 3-edge-colorable admits a cycle double cover (cf., e.g. [Ja85]). Since every cycle double cover C1, ..., Cq of a cubic graph G determines an embedding of G such that C1, ..., Cq are the facial cycles, Conjecture 5.5.15 restricted to cubic graphs is equivalent to the Cycle Double Cover Conjecture. Perhaps there is a fixed upper bound on the face-width of non-3-edge-colorable cubic graphs.

Problem 5.5.17 (Robertson). Is there a fixed constant k such that every 3-connected cubic graph with an embedding of face-width at least k has a 3-edge-coloring.

The Petersen graph in the projective plane shows that k is at least 4. Grünbaum [Gr69] conjectured that k = 3 may do if we consider only orientable embeddings. 

Alspach, Zhang, and Goddyn [AZ93, AGZ94] proved that every 2-connected cubic graph with no Petersen graph minor has a cycle double cover. Tutte [Tu66b] conjectured that every 2-connected cubic graph with no Petersen graph minor has a 3-edge-coloring. Recently, Robertson, Sanders, Seymour, and Thomas (private communication) proved this conjecture. These results are related to the following relaxation of Conjecture 5.5.16.

Conjecture 5.5.18 (Zhang). Every 2-connected cubic graph with no Petersen graph minor has an orientable embedding of face-width 2 or more.

Problem 5.5.19. Let k > 1 be a fixed integer. Does there exist a polynomial time algorithm for deciding if a given graph G admits an embedding of face-width k or more? Can we find such an embedding in polynomial time if it exists?

Conjecture 5.5.16 suggests that the answer to Problem 5.5.19 is positive for k = 2. For k = 3, Mohar proved:

Theorem 5.5.20 (Mohar [Mo00]).  It is NP-complete to decide if a given graph G admits an embedding of face-width 3 or more.

The problem remains NP-complete also for the existence of orientable embeddings of face-width at least 3 of 6-connected graphs [Mo00].

Conjecture 5.8.5 (Fiedler, Huneke, Richter, Robertson [FHRR88p]). For each fixed nonorientable surface S, the genus of a graph embedded in S can be found in polynomial time.

D. Barnette and X. Zha (private communication) proposed the following conjectures.

Conjecture 5.9.3 (Barnette, 1982). Every triangulation of a surface of genus at least 2 contains a noncontractible surface separating cycle.

Ellingham and Zha have informed us that they have proved Conjecture 5.9.3 for triangulations of the double torus.

Conjecture 5.9.4 (Zha, 1991). Every graph embedded in a surface of genus at least 2 with face-width at least 3 contains a noncontractible surface separating cycle.

Richter and Vitray (private communication) proved that this holds provided the face-width is at least 11. Zha and Zhao [ZZ93] and Brunet, Mohar, and Richter [BMR96] improved their result by showing that face-width 6 (even 5 for nonorientable surfaces) is sufficient. In [BMR96], it is also proved that a graph embedded with face-width w in a surface of genus at least 2 contains [(w-9)/8] disjoint noncontractible and pairwise homotopic surface separating cycles. 

If Conjecture 5.9.3 is true, also the following may hold.

Conjecture 5.9.5. Let T be a triangulation of an orientable surface of genus g, and let h be a positive integer that is smaller than g. Then T contains a surface separating cycle C such that the two surfaces separated by C have genera h and g - h, respectively.

It is even possible that Conjecture 5.9.5 extends to all embeddings of face-width at least 3. 

Theorem 5.10.3. (Mohar and Robertson [MR96a])  Let S be a surface. There is a constant  p = p(S) such that, for every embedding Π of face-width 2 of a 2-connected planar graph G in S, there is a sequence of 2-, 3-, and 4-flippings such that the resulting embedding Π1 of G in S has the following property: There is an embedding Π0 of G in the plane and a set Q of at most p vertices of G such that the induced embeddings of Π1 and Π0 of any component of G - Q are the same.

Mohar and Robertson [MR96a] also proved a strengthening of Theorem 5.10.3 including embeddings of face-width 1. In addition, they proved that the Π-clockwise and the Π1-clockwise ordering around the vertices in the set Q cannot differ too much. 

Conjecture (Mohar and Robertson [Mo97c]). A result similar to Theorem 5.10.3 holds also for embeddings of graphs of bounded genus.

By Theorem 5.11.11 below, any 4-connected graph with n vertices and sufficiently large face-width has a spanning tree of maximum degree 3 such that at most n/1000 vertices have degree 3. At the 1995 Slovenian Conference on Graph Theory, Mohar proposed the following 

Conjecture (Mohar, 1995). Every 4-connected graph embedded in a surface of Euler genus g with sufficiently large face-width contains a spanning tree with maximum degree 3 such that the number of vertices of degree 3 is O(g). 

4-connected planar graphs are hamiltonian. This is not true for graphs on other surfaces, even if the face-width is arbitrarily large. The best result in this direction is Theorem 5.11.11 below (and its consequence mentioned after the theorem).

These results were motivated by the following long-standing open question of Grünbaum [Gr70] and Nash-Williams [NW73].

Problem 5.11.9 (Grünbaum [Gr70] and Nash-Williams [NW73]). Is every 4-connected graph on the torus Hamiltonian?

Yu [Yu97] proved the following conjecture of Thomassen [Th94].

Theorem 5.11.10 (Yu [Yu97]). Let G be a 5-connected triangulation of a surface with Euler genus g. If the face-width of G is at least 96(2g - 1), then G has a Hamilton cycle.

Problem 5.11.12. Does Theorem 5.11.10 generalize to arbitrary 5-connected embedded graphs with sufficiently large face-width?

As pointed out in [Th94], Theorem 5.11.10 does not extend to 4-connected triangulations. On the other hand, Böhme, Mohar, and Thomassen [BMT98p] proved:

Theorem 5.11.11. (Böhme, Mohar, and Thomassen [BMT98p]) For each nonnegative integer g there is a constant w(g) such that every 4-connected graph G embedded in a surface of Euler genus g with face-width at least w(g) contains two cycles C1, C2 whose union contains all vertices of G and such that the length of Ci is at least 0.999|V(G)|, i = 1,2.

Theorem 5.11.11 implies in particular the existence of a 2-walk and the existence of a 2-connected spanning subgraph of maximum degree 4 and a connected spanning subgraph of maximum degree 3 with almost all vertices of degree 2 in every 4-connected graph embedded with sufficiently large face-width. Böhme, Mohar, and Thomassen [BMT98p] also proved that for every nonnegative integer g, there are constants c(g) > 0 and p(g) > 0 such that every 4-connected graph of Euler genus at most g contains a cycle of length at least c(g)|V(G)| and contains p(g) paths which cover all vertices of G.

Chapter 6

We say that a graph G covers a graph H if there exists a map f: V(G) –> V(H) such that f is onto and for any vertex v of G, the restriction of f to N(v) is a bijection to N(f(v)). For example, the graphs of the icosahedron and the dodecahedron cover K6 and the Petersen graph, respectively (by identifying diametrically opposite vertices). More generally, for every projective planar graph H there exists a planar graph which covers H. (To see this, we first draw H in a disc where opposite points are identified. Now take two copies of that disc, rotate one of them by 180 degrees, and paste their boundaries together so that we obtain a graph on the sphere.) Negami asked if the converse holds.

Conjecture 6.5.3. (Negami [Ne88a])  If a connected graph H is covered by a planar graph, then H is planar or projective planar.

If G covers H, then every subgraph of H is covered by a subgraph of G. So it suffices to verify Conjecture 6.5.3 for subdivisions of graphs in Forb(N1). Moreover, if e is an edge of H that is not contained in a 3-cycle, then H/e is covered by the corresponding minor of G. Since any minor of a graph can be obtained by deleting edges and contracting edges that are not in 3-cycles, it suffices to verify the conjecture for the 35 minimal forbidden minors for the projective plane. Archdeacon (private communication) further reduced this problem to only two graphs, namely K7 - 3K2 = K1,2,2,2 and K4,4 - K2. Hlineny [Hl98] proved that K4,4 - K2 has no planar cover, and therefore Conjecture 6.5.3 is equivalent to

Conjecture 6.5.4. The graph K1,2,2,2 is not covered by a planar graph.

Problem 6.6.1. Is it true that every minimal forbidden subgraph for the torus contains less than 100 edges?

Glover asked if each edge of a minimally nonembeddable graph G (in any surface) is contained in a subgraph K of G which is a subdivision of K5 or K3,3. This question has been answered in the affirmative if S is nonorientable by Brunet, Richter, and Siran [BRS96]. They also observed that the minimal forbidden subgraph H for the torus represented in Figure 6.8 contains an edge ab which is not part of a Kuratowski subgraph of H. A more specific conjecture of Glover [GT87, p. 53] is still open:

Conjecture 6.6.2 (Glover).  Let G be a minimal forbidden subgraph for the nonorientable surface Nk. Then G can be written as the union of k+1 subgraphs each of which is a subdivision of K5 or K3,3.

Chapter 7

Problem 7.3.4. Let w0 be any fixed integer. Does there exist a polynomially bounded algorithm to find the (orientable) genus of any graph of tree-width less than w0?

This problem has been answered in the affirmative by Mohar [1].

Chapter 8

Problem 8.4.10. Let S be a fixed surface. Does there exist a polynomially bounded algorithm for deciding if a graph on S can be 4-colored.

Problem 8.4.14 (Thomassen [Th95p]. Does some surface have 5-critical triangulations of arbitrarily large edge-width?

Problem 8.4.15 (Albertson [Al81]). Let S be any surface. Does there exist a natural number q = q(S) such that any graph G on S contains a set A of at most q vertices such that G - A is 4-colorable?

Problem 8.4.15 is open even for the torus where possibly q=3 will do as conjectured by Albertson [Al81].

Theorem 8.5.7 (Fisk and Mohar [FM94b]; Gimbel and Thomassen [GT97]).
    (1) If S is a surface and k greater or equal to 5, then there are only finitely many k-critical, triangle-free graphs on S.
    (2) If S is a surface and k greater or equal to 4, then there are only finitely many k-critical graphs of girth at least 6 on S.

Theorem 8.5.7 shows that, for each fixed surface S, the chromatic number of a graph of girth 6 on S can be found in polynomial time. Also, it can be decided in polynomial time if a triangle-free graph on S can be 4-colored. This raises the following questions.

Problem 8.5.8 (Gimbel and Thomassen [GT97]). Does there exist a surface S and an infinite family of 4-critical graphs of girth 5 that can be embedded in S?

Thomassen [Th94b] proved that there are no such graphs on the torus or the projective plane.

Problem 8.5.9 (Gimbel and Thomassen [GT97]). Let S be any fixed surface. Can the chromatic number of a triangle-free graph on S be found in polynomial time?

References:

Almost all stated references can be found in the book under the same abbreviations.

Additional references are:

[1] B. Mohar, Genus of graphs of bounded tree-width, in preparation.

[2] R. Diestel, Graph Theory, Springer, 1997.

[3] W. Mader, Graphs with 3n - 6 edges not containing a subdivision of K5, submitted to Combinatorica, 2002.

 

Send comments to Bojan.Mohar@uni-lj.si

Revised: October 16, 2009.