Removable Edges and Chords of Longest Cycles in 3-Connected Graphs

2014 
We verify two special cases of Thomassen's conjecture of 1976 stating that every longest cycle in a 3-connected graph contains a chord.We prove that Thomassen's conjecture is true for two classes of 3-connected graphs that have a bounded number of removable edges on or off a longest cycle. Here an edge e of a 3-connected graph G is said to be removable if G --- e is still 3-connected or a subdivision of a 3-connected (multi)graph.We give examples to showthat these classes are not covered by previous results.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    13
    References
    3
    Citations
    NaN
    KQI
    []