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''.
[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 email@example.com and to firstname.lastname@example.org