David R. Wood

Title: David R. Wood

Research Question: The study aims to characterize various types of intersection graphs, such as interval graphs, comparability graphs, co-comparability graphs, permutation graphs, and split graphs, using vertex orderings. It also explores the bandwidth of these graphs.

Methodology: The research uses vertex orderings to characterize the mentioned intersection graphs. It presents a theorem that states a graph is an interval graph if and only if it has a vertex ordering such that certain conditions are met. It also provides a proper interval graph characterization and discusses the bandwidth of these graphs.

Results: The study presents several theorems and characterizations for different types of intersection graphs. It proves that interval graphs, co-comparability graphs, AT-free graphs, and split graphs have bandwidth bounded by their maximum degree.

Implications: The results of this research have implications for the field of graph theory. The characterizations provided can be used to better understand and study these types of graphs. The bandwidth results can also be useful in applications where bandwidth is a concern, such as in computer networking and data communication.

Link to Article: https://arxiv.org/abs/0404031v1 Authors: arXiv ID: 0404031v1