Subthrackleable Graphs and 4 Cycles
Mathematics and Natural Sciences
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.
Piazza, B. L.,
(1994). Subthrackleable Graphs and 4 Cycles. Discrete Mathematics, 127(1-3), 265-276.
Available at: https://aquila.usm.edu/fac_pubs/7219