The 54\frac{5}{4}-tough spanning 2-trail conjecture for 2K22K_2-free graphs

A graph is 2K22K_2-free if it has no induced subgraph consisting of two independent edges, and it is tt-tough if Stc(GS)|S|\geq t\,c(G-S) whenever deletion of SS leaves at least two components. A spanning 2-trail is a spanning trail with maximum degree at most 44.

The 54\frac{5}{4}-tough spanning 2-trail conjecture. Any 54\frac{5}{4}-tough 2K22K_2-free graph with at least three vertices has a spanning 2-trail.

The paper constructs 2K22K_2-free graphs with toughness approaching 54\frac{5}{4} 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.