Title

Subthrackleable Graphs and 4 Cycles

Document Type

Article

Publication Date

3-15-1994

Department

Mathematics

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