Interpolation Conjectures on Separating Cycles in Embedded Graphs

A well-known problem, attributed to Barnette, asks if every triangulation of a surface whose genus is at least two contains a noncontractible cycle that is homologically trivial (a surface separating cycle). Zha and Zhao conjectured that the same holds for any graphs embedded in a surface of genus g at least 2 if the face-width of the embedding is at least three. (The face-width of a graph G embedded in a surface S is the minimum number of points in C intersect G taken over all noncontractible C in S.) More generally, Thomassen conjectured that given a triangulation T of a surface of genus g and a number h strictly less than g, T must contain a surface separating cycle C such that the two surfaces separated by C have genus h and g-h, respectively. Combining these two generalizations yields the following conjecture.

Conjecture: Suppose that G is embedded in a surface of genus g with face-width three or more. Then for every integer h less than g, G contains a surface separating cycle C such that the two surfaces separated by C have genus h and g-h, respectively.

In a similar problem, Mohar and Robertson [MR] characterized embeddings of graphs which do not have two disjoint noncontractible cycles. In relation to their results they proposed the following interpolation conjecture.

Conjecture: Suppose that G admits embeddings in orientable surfaces of genus h and g such that each of these embeddings contains two disjoint noncontractible cycles. Then for every k between h and g, there is an embedding in a surface of genus k which has at least two disjoint essential cycles.

See also the problems posed by Rick Vitray on ``Finding Separating Cycles in Embedded Graphs''.

References:

[MR] B. Mohar and N. Robertson, Disjoint essential cycles, in preparation.

Submitted by: Bojan Mohar, Department of Mathematics, University of Ljubljana, Jadranska 19, 61111 Ljubljana, Slovenia

Send comments to dan.archdeacon@uvm.edu and to bojan.mohar@uni-lj.si