Subthrackleable Graphs and 4 Cycles
Document Type
Article
Publication Date
3-15-1994
Department
Mathematics
School
Mathematics and Natural Sciences
Abstract
According to Conway as quoted in a paper by Woodall a graph is ‘thrackled’ if it can be drawn with every edge crossing every other ‘eligible’ one. The thrackle conjecture, which remains unsolved, states that any such graph with n vertices can have at most n edges. Since a four cycle is unable to be ‘thrackled’ a new upper bound for maximum crossings is demonstrated in a previous paper, taking into account this factor. In this paper we call a graph ‘subthrackleable’ if it meets this new upper bound and several subthrackleable graphs are given, with a concentration on those with several four cycles. We also demonstrate that there are many graphs which are not subthrackleable.
Publication Title
Discrete Mathematics
Volume
127
Issue
1-3
First Page
265
Last Page
276
Recommended Citation
Piazza, B. L.,
Ringeisen, R.,
Stueckle, S.
(1994). Subthrackleable Graphs and 4 Cycles. Discrete Mathematics, 127(1-3), 265-276.
Available at: https://aquila.usm.edu/fac_pubs/7219