1-tough cocomparability graphs are hamiltonian
From MaRDI portal
Publication:1363656
DOI10.1016/0012-365X(95)00359-5zbMATH Open0876.05066MaRDI QIDQ1363656FDOQ1363656
Dieter Kratsch, George Steiner, Jitender Deogun
Publication date: 10 August 1997
Published in: Discrete Mathematics (Search for Journal in Brave)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- An optimal path cover algorithm for cographs
- Finding Hamiltonian circuits in interval graphs
- Toughness, hamiltonicity and split graphs
- Tough graphs and Hamiltonian circuits.
- On a class of posets and the corresponding comparability graphs
- On Maximal Circuits in Finite Graphs
- Long cycles in graphs with large degree sums
- Computing the bump number is easy
- Computing the bump number with techniques from two-processor scheduling
- Hamiltonicity in graphs with few \(P_ 4\)'s
- Hamiltonian degree conditions for tough graphs
- Recognizing tough graphs is NP-hard
- An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
- An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
- Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
- Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
- Toughness and the existence ofk-factors
- On the complexity of recognizing tough graphs
Cited In (22)
- Toughness in graphs -- a survey
- Title not available (Why is that?)
- Toughness and Hamiltonicity in \(k\)-trees
- The scattering number of strictly chordal graphs: linear time determination
- Toughness and Hamiltonicity of strictly chordal graphs
- Title not available (Why is that?)
- Hamiltonicity of 1-tough \((P_2 \cup KP_1)\)-free graphs
- Characterization of interval graphs that are unpaired 2-disjoint path coverable
- Hamiltonian powers in threshold and arborescent comparability graphs
- Title not available (Why is that?)
- Assistance and interdiction problems on interval graphs
- The scattering number of thorn graphs
- On Toughness and Hamiltonicity of 2K2‐Free Graphs
- Chvátal’s t 0-Tough Conjecture
- Hamiltonian cycles in 7-tough \((P_3 \cup 2P_1)\)-free graphs
- Semi-proper interval graphs
- Some properties of \(k\)-trees
- Disjoint path covers joining prescribed source and sink sets in interval graphs
- Toughness, hamiltonicity and split graphs
- Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs
- Vulnerability of subclasses of chordal graphs
- Cyclability in graph classes
This page was built for publication: 1-tough cocomparability graphs are hamiltonian
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1363656)
