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 language||English (US)|
|Number of pages||8|
|State||Published - Jun 10 1997|
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics