Bounds for generalized thrackles

被引:51
作者
Cairns, G [1 ]
Nikolayevsky, Y [1 ]
机构
[1] La Trobe Univ, Dept Math, Bundoora, Vic 3083, Australia
关键词
General Setting; Bipartite Graph; Closed Surface; Connected Surface; Orientable Connected Surface;
D O I
10.1007/PL00009495
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
A thrackle (resp. generalized thrackle) is a drawing of a graph in which each pair of edges meets precisely once (resp. an odd number of times). For a graph with n vertices and m edges, we show that, for drawings in the plane, m less than or equal to 3/2 (n - 1) far thrackles, while m less than or equal to 2n - 2 for generalized thrackles. This improves theorems of Lovasz, Pach, and Szegedy. The paper also examines thrackles in the more general setting of drawings on closed surfaces. The main result is: a bipartite graph G can be drawn as a generalized thrackle on a closed orientable connected surface if and only if G can be embedded in that surface.
引用
收藏
页码:191 / 206
页数:16
相关论文
共 12 条
[1]  
Croft H. T., 1991, SPRINGER SCI BUSINES
[2]  
DUBROVIN BA, 1990, MODERN GEOMETRY 3
[3]  
Fulton W., 1995, Graduate Texts in Mathematics, V153
[4]  
GREEN JE, 1995, GRAPH THEORY COMBINA, V1, P999
[5]  
Gross J.L., 1987, Topological graph theory
[6]   On Conway's thrackle conjecture [J].
Lovasz, L ;
Pach, J ;
Szegedy, M .
DISCRETE & COMPUTATIONAL GEOMETRY, 1997, 18 (04) :369-376
[7]  
PACH J, 1995, COMBINATORIAL GEOMET
[8]   SUBTHRACKLEABLE GRAPHS AND 4 CYCLES [J].
PIAZZA, BL ;
RINGEISEN, RD ;
STUECKLE, SK .
DISCRETE MATHEMATICS, 1994, 127 (1-3) :265-276
[9]  
RINGEISEN RD, 1996, C NUMER, V115, P91
[10]  
SEIFERT H, 1980, TXB TOPOOGY