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

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

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

We were informed by Wolfgang Mader that Conjecture 2.5.7 follows from his
characterization of graphs on * n* vertices with 3*n*-6 edges not containing a subdivision
of K_{5} [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 K_{5}.

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

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

**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.

**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*?

[S. Cabello, Finding shortest contractible and shortest separating cycles in embedded graphs, SODA'09]. From the abstract of that paper: "

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

**Problem.**
Prove that **g**(K_{3,3,3,3}) > 4.

This problem is equivalent to the statement that K_{3,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**(K_{3,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?

**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?

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

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

**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.

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?

**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.

**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.

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

**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.

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.

**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.

**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(2* ^{g}* - 1), then

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

**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 *C*_{1}*,
C*_{2} whose union contains all vertices of *G*
and such that the length of *C _{i}* is at least 0.999|V(G)|,

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

**Conjecture 6.5.4.**
The graph K_{1,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?

**Conjecture 6.6.2 (Glover).**
Let *G* be a minimal forbidden subgraph for the nonorientable surface **N*** _{k}*. Then

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

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

**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?

**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?

**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 3*n* - 6 edges not containing a subdivision of
*K*_{5}, submitted to Combinatorica, 2002.

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