1-tough cocomparability graphs are hamiltonian

Jitender S. Deogun, Dieter Kratsch, George Steiner

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


We show that every 1-tough cocomparability graph has a Hamilton cycle. This settles a conjecture of Chvàtal for the case of cocomparability graphs. Our approach is based on exploiting the close relationship of the problem to the scattering number and the path cover number.

Original languageEnglish (US)
Pages (from-to)99-106
Number of pages8
JournalDiscrete Mathematics
Issue number1-3
StatePublished - Jun 10 1997
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of '1-tough cocomparability graphs are hamiltonian'. Together they form a unique fingerprint.

Cite this