Finding Separating Cycles in Embedded Graphs
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.
Question: What is the smallest value of n which implies that any embedding of face-width n in a surface of genus at least 2 must contain an essential separating polygon?
Zha and Zhao [ZZ] conjecture that face-width 3 suffices for the above. For orientable surfaces the value is known to lie between 3 and 6 [ZZ,BMR]. For nonorientable surfaces the value is less than or equal to 5 [ZZ]. It would be nice to have an example giving a lower bound of 3 for nonorientable surfaces.
Two related problems follow.
Prove or Disprove: In any face-width 2 embedding either the primal graph or the dual graph must contain an essential separating polygon.
Prove or Disprove: If a face-width 3 embedding of a graph contains an essential separating polygon, then the dual must also.
If the latter two conjectures are true, then the answer to the first question is n = 3.
Bojan Mohar proposes some related questions under the title ``Interpolation Conjectures on Separating Cycles in Embedded Graphs''. See also [M].
An unrelated and less precise question is related to other work I've been involved with.
Problem: Characterize classes of face-width 3 embeddings on a surface in which the number of faces does not exceed the number of vertices.
[BMR] R. Brunet, B. Mohar, and R.B. Richter, On the homotopy of cycles in graph embeddings, preprint (1992).
[M] B. Mohar and N. Robertson, Disjoint essential cycles, in preparation.
[ZZ] X.Y. Zha and Y. Zhao, On nonnull separating circuits in embedded graphs, in ``Graph Structure Theory (Seattle, WA 1991)'', Contemp. Math. 147 American Math. Soc., Providence RI (1993) 349-363.
Submitted by: Rick Vitray, Math. Dept., Rollins College, Orlando, FL.
Send comments to email@example.com and to firstname.lastname@example.org