1-tough cocomparability graphs are hamiltonian
From MaRDI portal
Publication:1363656
DOI10.1016/0012-365X(95)00359-5zbMath0876.05066MaRDI QIDQ1363656
George Steiner, Dieter Kratsch, Jitender S. Deogun
Publication date: 10 August 1997
Published in: Discrete Mathematics (Search for Journal in Brave)
cocomparability graphs; Hamilton cycle; scattering number; path cover number; 1-tough cocomparability graph
Related Items
The scattering number of thorn graphs, Unnamed Item, Toughness and Hamiltonicity in \(k\)-trees, Hamiltonian powers in threshold and arborescent comparability graphs, Toughness, hamiltonicity and split graphs, Toughness in graphs -- a survey
Cites Work
- Unnamed Item
- Unnamed Item
- Long cycles in graphs with large degree sums
- An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
- Recognizing tough graphs is NP-hard
- Finding Hamiltonian circuits in interval graphs
- Computing the bump number is easy
- Computing the bump number with techniques from two-processor scheduling
- Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
- On a class of posets and the corresponding comparability graphs
- On the complexity of recognizing tough graphs
- Hamiltonicity in graphs with few \(P_ 4\)'s
- Hamiltonian degree conditions for tough graphs
- An optimal path cover algorithm for cographs
- Toughness, hamiltonicity and split graphs
- Tough graphs and Hamiltonian circuits.
- Toughness and the existence ofk-factors
- An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
- On Maximal Circuits in Finite Graphs
- Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
