Characterisations of intersection graphs by vertex orderings

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

Characterisations of interval graphs, comparability graphs, co-comparability graphs, permutation graphs, and split graphs in terms of linear orderings of the vertex set are presented. As an application, it is proved that interval graphs, co-comparability graphs, AT-free graphs, and split graphs have bandwidth bounded by their maximum degree.
Original languageEnglish
Pages (from-to)261-268
Number of pages8
JournalAustralasian Journal of Combinatorics
Volume34
Publication statusPublished - 2006
Externally publishedYes

Cite this