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*