Characterisations of Intersection Graphs by Vertex Orderings

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.

submitted

Cited by in corpus (3)

• Graph Drawings with Few Slopes
• Really Straight Graph Drawings
• Classifying grounded intersection graphs via ordered forbidden patterns