We prove that there exists a function a: N-0 x R_ --> N such that (i) If G is a 4-connected graph of order n embedded on a surface of Euler genus g such that the face-width of G is at least a(g, e), then G can be covered by two cycles each of which has length at least (1-epsilon) n. We apply this to derive lower bounds for the length of a longest cycle in a graph G on any fixed surface. Specifically, there exist functions b: N-0 --> N and c: N-0 --> R+ such that for every graph G on n vertices that is embedded on a surface of Euler genus g the following statements hold: (ii) If G is 4-connected, then G contains a collection of at most 6(g) paths which cover all vertices of G, and G contains a cycle of length at least n/b(g). (iii) If G is 3-connected, then G contains a cycle of length at least c( g) n(log2/log3), Moreover, for each epsilon > 0, every 4-connected graph G with sufficiently large face-width contains a spanning tree of maximum degree at most 3 and a 2-connected spanning subgraph of maximum degree at most 4 such that the number of vertices of degree 3 or 4 in either of these subgraphs is at most epsilon V(G). (C) 2002 Elsevier Science (USA). [References: 24]
展开▼
机译：我们证明存在一个函数a：N-0 x R_-> N使得（i）如果G是嵌入在Euler属g的表面上的n阶4连通图，则G的面宽如果a至少为a（g，e），则G可以被两个周期覆盖，每个周期的长度至少为（1-ε）n。我们将其应用于在任何固定表面上的图形G中最长循环的长度的下界。具体来说，存在函数b：N-0-> N和c：N-0-> R +，使得对于嵌入在Euler属g的曲面上的n个顶点上的每个图G，以下语句均成立：（ii ）如果G是4连接的，则G包含最多6个（g）路径的集合，这些路径覆盖G的所有顶点，并且G包含长度至少为n / b（g）的循环。 （iii）如果G是3个连通的，则G包含一个长度至少为c（g）n（log2 / log3）的循环，而且，对于每个epsilon> 0，每个4个连通的图G具有足够大的面宽包含最大度数为3的生成树和最大度数为4的2连通生成子图，使得这些子图中任一度数的3或4的顶点数最多为epsilon V（G）。 （C）2002 Elsevier Science（美国）。 [参考：24]
展开▼
