The -tough spanning 2-trail conjecture for -free graphs
The -tough spanning 2-trail conjecture for -free graphs
A graph is -free if it has no induced subgraph consisting of two independent edges, and it is -tough if whenever deletion of leaves at least two components. A spanning 2-trail is a spanning trail with maximum degree at most .
The -tough spanning 2-trail conjecture. Any -tough -free graph with at least three vertices has a spanning 2-trail.
The paper constructs -free graphs with toughness approaching that have no spanning 2-trail, motivating this threshold conjecture; no proof or refutation is given in the supplied text.
Sources & referencesView supporting material
Primary source
Guantao Chen, M. N. Ellingham, Akira Saito and Songling Shan, “Spanning trails with maximum degree at most 4 in 2K_2-free graphs”, arXiv:1609.08730 (2016).
Additional references
2 papers in this index state this conjecture (2014–2016). The statement above is taken from the most recent of them; the others are arXiv:1408.3380.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.