Characterisations of Intersection Graphs\\ by Vertex Orderings\,\thanks{Research supported by NSERC and COMBSTRU.}
David R. Wood
[1ex] School of Computer Science
Ottawa
Canada
[0.5ex] Department of Applied Mathematics
Prague
Czech Republic
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.
Wood-IntersectionGraphOrdering.tex
\documentclass[12pt]{article}

\usepackage{amsthm,amsfonts,amsmath,graphicx}
\usepackage[sort&compress,numbers]{natbib}

\input{myTheorems}
\input{myLabels}
\input{myCommands}

\newcommand{\aaa}{\textup{(a)}}
\newcommand{\bbb}{\textup{(b)}}
\newcommand{\ccc}{\textup{(c)}}
\newcommand{\ddd}{\textup{(d)}}
\newcommand{\eee}{\textup{(e)}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\setlength{\textwidth}{6.3in}
\setlength{\textheight}{8.7in}
\setlength{\topmargin}{0pt}
\setlength{\headsep}{0pt}
\setlength{\headheight}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}

%\makeatletter
%\newfont{\footsc}{cmcsc10 at 8truept}
%\newfont{\footbf}{cmbx10 at 8truept}
%\newfont{\footrm}{cmr10 at 10truept}
%\renewcommand{\ps@plain}{%
%\renewcommand{\@oddfoot}{\footsc the electronic journal of combinatorics
%  {\footbf 11} (2004), \#R00\hfil\footrm\thepage}}
%\makeatother
\pagestyle{plain}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{\textbf{Characterisations of Intersection Graphs\\ by Vertex
Orderings}\,\thanks{Research supported by NSERC and COMBSTRU.}}

\author{David R. Wood\\[1ex]
\small School of Computer Science\\[-0.8ex]
\small Carleton University, Ottawa, Canada\\[0.5ex]
\small Department of Applied Mathematics\\[-0.8ex]
\small Charles University, Prague, Czech Republic\\[0.5ex]
\small \texttt{davidw@scs.carleton.ca}
}

%\date{\small Submitted: March 31, 2004;  Accepted: ??? ?, ????;
% Published: ??? ?, ????\\
%\small MR Subject Classifications: 05C88, 05C89}

\begin{document}
\maketitle

\begin{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. 
\end{abstract}

\section{Introduction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We consider finite, simple and undirected graphs $G$ with vertex set $V(G)$,
edge set $E(G)$, and maximum degree $\Delta(G)$. The \emph{compliment} of $G$
is the graph $\overline{G}$ with vertex set $V(G)$ and edge set $\{vw:v,w\in
V(G),vw\not\in E(G)\}$. A \emph{vertex ordering} of $G$ is a total order
$(v_1,v_2,\dots,v_n)$ of $V(G)$. Let $\mathcal{S}$ be a finite family of sets. 
The \emph{intersection graph} of $\mathcal{S}$ has vertex set $\mathcal{S}$ and
edge set $\{AB:A,B\in S,A\cap B\ne\emptyset\}$.  This paper presents
characterisations of a number of popular intersection graphs in terms of vertex
orderings. 

In a vertex ordering $(v_1,v_2,\dots,v_n)$ of a graph $G$, the \emph{width} of
an edge $v_iv_j\in E(G)$ is $|i-j|$. The maximum width of an edge is the
\emph{width} of the ordering. The \emph{bandwidth} of $G$ is the minimum width
of a vertex ordering of $G$. Bandwidth is a ubiquitous concept with numerous
applications (see \citep{CCDG-Bandwidth-JGT82}). Obviously the bandwidth of $G$
is at least $\half\Delta(G)$. As an application of our results, we prove upper
bounds on the bandwidth of many intersection graphs $G$ in terms of
$\Delta(G)$. 

\section{Interval Graphs}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

An \emph{interval graph} is the intersection graph of a finite set of closed
intervals in $\mathbb{R}$.  We have the following characterisation of interval
graphs.

\begin{theorem}
\thmlabel{Interval}
A graph $G$ is an interval graph if and only if $G$ has a vertex ordering
$(v_1,v_2,\dots,v_n)$ such that 
\begin{equation}
\eqnlabel{Interval}
\forall\,i<j<k,\;v_iv_k\in E(G)\;\Rightarrow\;v_iv_j\in E(G)\enspace.
\end{equation}
\end{theorem}

\begin{proof} Let  $(v_1,v_2,\dots,v_n)$ be a vertex ordering of $G$ satisfying
\eqnref{Interval}. For each vertex $v_i$, associate the interval $[i,r(i)]$,
where $v_{r(i)}$ is the rightmost neighbour of $v_i$. For every edge $v_iv_j\in
E(G)$ with $i<j$, $j\in[i,r(i)]\cap[j,r(j)]$.  For every non-edge $v_iv_j\in
E(\overline{G})$ with $i<j$, we have $r(i)<j$ by \eqnref{Interval}, and 
$[i,r(i)]\cap[j,r(j)]=\emptyset$.  Hence the intersection graph of
$\{[i,r(i)]:v_i\in V(G)\}$ is $G$.

Let $G$ be an interval graph. It is well known that we can assume that the
endpoints of the intervals are distinct. Let $(v_1,v_2,\dots,v_n)$ be a vertex
ordering of $G$ determined by increasing values of the left endpoints of the
intervals. For all $i<j<k$, the left endpoint of $v_j$ is between the left
endpoints of $v_i$ and $v_k$. If $v_iv_k\in E(G)$ then the right endpoint of
$v_i$ is to the right of the left endpoint of $v_k$. Thus the left endpoint of
$v_j$ is in the interval for $v_i$. Hence $v_iv_j\in E(G)$, as
claimed.
\end{proof}

As far as we are aware, \thmref{Interval} has not appeared in the literature,
although similar results are known. For example, \citet{GilmoreHoffman-CJM64}
proved that $G$ is an interval graph if and only if there is an ordering of the
maximal cliques of $G$ such that for each vertex $v$, the maximal cliques
containing $v$ appear consecutively.

\thmref{Interval} implies the following result of \citet{FominGolovach-DAM03}.

\begin{corollary}[\citep{FominGolovach-DAM03}]
Every interval graph $G$ has bandwidth at most $\Delta(G)$.
\end{corollary}

\begin{proof} In the vertex ordering  $(v_1,v_2,\dots,v_n)$ from
\thmref{Interval}, the width of an edge $v_iv_k\in E(G)$ is  $|\{v_iv_j\in
E(G):i<j\leq k\}|\leq\deg(v_i)\leq\Delta(G)$. \end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

A \emph{proper interval graph} is the intersection graph of a finite set
$\mathcal{S}$ of closed intervals in $\mathbb{R}$ such that $A\not\subset B$
for all $A,B\in\mathcal{S}$. The following characterisation is due to
\citet{LoogesOlariu93} (see \citep{Corneil-DAM04}).

\begin{theorem}[\citep{LoogesOlariu93}]
\thmlabel{ProperInterval}
A graph $G$ is a proper interval graph if and only if $G$ has a vertex ordering
$(v_1,v_2,\dots,v_n)$ such that,
\begin{equation}
\eqnlabel{ProperInterval}
\forall\,i<j<k,\;v_iv_k\in E(G)\;\Rightarrow\;v_iv_j\in E(G)\;\wedge\;v_jv_k\in E(G)\enspace.
\end{equation}
\end{theorem}

It is easily seen that the bandwidth of a proper interval graph is one less
than the maximum clique size. Moreover, \citet{KaplanShamir-SJC96} proved that
the bandwidth of any graph $G$ equals the minimum, taken over all proper
interval supergraphs $G'$ of $G$, of the bandwidth of $G'$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Comparability Graphs}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Let $(P,\preceq)$ be a poset.  The \emph{comparability graph} of $(P,\preceq)$
has vertex set $P$, and distinct elements are adjacent if and only if they are
comparable under $\preceq$. We have the following characterisation of
comparability graphs. 

\begin{theorem}
\thmlabel{Comparability}
The following are equivalent for a graph $G$:\\
\aaa\ $G$ is a comparability graph,\\
\bbb\ $G$ has a vertex ordering $(v_1,v_2,\dots,v_n)$ such that,
\begin{equation}
\eqnlabel{Comparability}
\forall\,i<j<k,\;v_iv_j\in E(G)\;\wedge\;v_jv_k\in E(G)
\;\Rightarrow\;v_iv_k\in E(G)\enspace.
\end{equation}
\end{theorem}

\begin{proof} Let $G$ be the comparability graph of a poset $(V(G),\preceq)$.
A linear extension of $\preceq$ satisfies \eqnref{Comparability}. Given a
vertex ordering that satisfies \eqnref{Comparability},  define $v_i\prec v_j$
whenever $v_iv_j\in E(G)$ and $i<j$. Thus $(V(G),\preceq)$ is a poset, and $G$
is a comparability graph.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

A \emph{co-comparability graph} is a compliment of a comparability graph. As
illustrated in \figref{FunctionDiagram},  a \emph{function diagram} is a set
$\{c_i:1\leq i\leq n\}$, where for each $c_i$ is a curve $\{(x,f_i(x)):0\leq
x\leq 1\}$ for some function  $f_i:[0,1]\rightarrow\mathbb{R}$. If each $c_i$
is a line segment we say  $\{c_i:1\leq i\leq n\}$ is \emph{linear}.

\begin{figure}[hbt]
\vspace*{1ex}
\begin{center}\includegraphics{FunctionDiagram}\end{center}
\vspace*{-2ex}
\caption{\figlabel{FunctionDiagram}A vertex ordering of the intersection graph of a function diagram.}
\end{figure}

\begin{theorem}
\thmlabel{CoComparability}
The following are equivalent for a graph $G$:\\
\aaa\ $G$ is a co-comparability graph,\\
\bbb\ $G$ is the intersection graph of a function diagram, and \\
\ccc\ $G$ has a vertex ordering $(v_1,v_2,\dots,v_n)$ such that,
\begin{equation}
\eqnlabel{CoComparability}
\forall\,i<j<k,\;
v_iv_k\in E(G)\;\Rightarrow\;v_iv_j\in E(G)\;\vee\;v_jv_k\in E(G)\enspace.
\end{equation}
\end{theorem}

\begin{proof} \citet{KGK86} and \citet{GRU-DM83} independently proved that
\aaa\ and \bbb\ are equivalent.

We now prove that \ccc\ implies \aaa. 
Suppose that $G$ has a vertex ordering
$(v_1,v_2,\dots,v_n)$ satisfying \eqnref{CoComparability}.
Define $v_i\prec v_j$ if $i<j$ and $v_iv_j\not\in E(G)$. 
Obviously $\prec$ is antisymmetric.
Suppose $v_i\prec v_j$ and $v_j\prec v_k$.
Then $i<k$ and $v_iv_k\not\in E(G)$, as otherwise 
\eqnref{CoComparability} fails.
That is, $v_i\prec v_k$. 
Thus $\prec$ is transitive, 
and $(V(G),\preceq)$ is a poset, whose
comparability graph is $\overline{G}$. 
Therefore $G$ is a co-comparability graph.

We now prove that \bbb\ implies \ccc.
Let $G$ be the intersection graph of a  function diagram 
$\{c_i:1\leq i\leq n\}$   with corresponding functions $\{f_i:1\leq i\leq n\}$.
Re-index so that  $f_i(0)\leq f_{i+1}(0)$ for all
$1\leq i\leq n-1$.  
Associate a vertex $v_i$ with each function $f_i$.   
Consider an edge $v_iv_k\in E(G)$ and a vertex $v_j$ with $i<j<k$.
There is a region $S$ bounded by $c_i$, $c_k$, and the line $X=0$, such that 
$c_j$ intersects the closed interior of $S$ and the closed exterior of $S$.
Thus $c_j$ intersects the boundary of $S$. Since $f_j$ is a function on
$[0,1]$, $c_j$ intersects the boundary of $S$ at a point on $c_i$ or $c_k$.
Thus $c_i\cap c_j\ne\emptyset$ or $c_j\cap c_k\ne\emptyset$.
Hence $v_iv_k\in E(G)$ or $v_jv_k\in E(G)$. 
That is, the vertex ordering $(v_1,v_2,\dots,v_n)$ satisfies
\eqnref{CoComparability}.
%
%If $f_i(0)=f_j(0)$ or $f_j(0)=f_k(0)$, then we are done.
%Now assume that $f_i(0)<f_j(0)<f_k(0)$.
%Since $v_iv_k\in E(G)$, $c_i\cap c_j\ne\emptyset$.
%Let $x_0=\min\{x\in(0,1]:f_i(x)=f_k(x)\}$. 
%Define 
%$$S=\{(0,y):f_i(0)\leq y\leq f_k(0)\}
%\cup\{(x,f_i(x)):0\leq x\leq x_0\}
%\cup\{(x,f_k(x)):0\leq x\leq x_0\}\enspace.$$
%Observe that $S$ is a simple closed curve.
%Let $S_I$ be the open region on the inside of $S$, and 
%let $S_O$ be the closed region on the outside of $S$.
%Thus $f_j(1)\in S_O$.
%Since $f_i(0)<f_j(0)<f_k(0)$,
%there exists $\epsilon>0$ such that $f_j(\epsilon)\in S_I$.
%Thus $c_j$ intersects $S$.
%Since $f_j$ is a function on $[0,1]$, $c_j$ intersects $S$ at a point $(x,y)$
%or some $x>0$.
%Thus  $c_i\cap c_j\ne\emptyset$ or $c_j\cap c_k\ne\emptyset$, as claimed. 
Note that we could have ordered the vertices with respect to  any fixed value
of $x_0\in[0,1]$, and in general, there are many vertex orderings that satisfy
\eqnref{CoComparability}.
\end{proof}

\begin{corollary}
\corlabel{CoComparabilityBandwidth}
Every co-comparability graph $G$ has bandwidth at most $2\Delta(G)-1$.
\end{corollary}

\begin{proof} In the vertex ordering $(v_1,v_2,\dots,v_n)$ from
\thmref{CoComparability}, the width of an edge $v_iv_k\in E(G)$ is at most
$|\{v_iv_j\in E(G):i<j<k\}|+|\{v_jv_k\in E(G):i<j<k\}|+1\leq
(\deg(v_i)-1)+(\deg(v_k)-1)+1\leq2\Delta(G)-1$. \end{proof}

It is interesting to ask whether \corref{CoComparabilityBandwidth} is
tight. It is easily seen that the complete bipartite graph $K_{n,n}$, which is
a co-comparability graph with maximum degree $n$, has bandwidth $3n/2$. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\medskip Let $\pi$ be a permutation of $\{1,2,\dots,n\}$.  Let $\pi^{-1}(i)$
denote the position of $i$ in $\pi$. The \emph{permutation graph}  associated
with $\pi$ has vertex set $\{v_1,v_2,\dots,v_n\}$ and edge set
$\{v_iv_j:(i-j)(\pi^{-1}(i)-\pi^{-1}(j))<0\}$. The following characterisations of
permutation graphs can be derived from results of \citet{DushnikMiller41} and
\citet{BFR-Networks72}. Part (e) is proved as in
\twothmref{Comparability}{CoComparability}.

\begin{theorem}[\citep{DushnikMiller41,BFR-Networks72}]
\thmlabel{Permutation}
The following are equivalent for a graph $G$:\\
\aaa\ $G$ is a permutation graph,\\
\bbb\ $G$ is the intersection graph of a linear function diagram,\\
\ccc\ $G$ is a comparability graph and a co-comparability graph,\\
\ddd\ $G$ is the comparability graph of a two-dimensional poset,\\
\eee\ $G$ has a vertex ordering that simultaneously 
satisfies \eqnref{Comparability} and \eqnref{CoComparability}.
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{AT-free Graphs}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

An \emph{asteroidal triple} in a graph consists of an independent set of three
vertices such that each pair is joined by a path that avoids the neighbourhood
of the third. A graph is \emph{asteroidal triple-free} (\emph{AT-free}) if it
contains no asteroidal triples. 

%\COMMENT{Is there a characterisation of AT-free graphs in terms of a vertex
%ordering?}

\begin{lemma}
Every AT-free graph $G$ has bandwidth at most $3\Delta(G)$.
\end{lemma}

\begin{proof} A \emph{caterpillar} is a tree for which a path (called the
spine) is obtained by deleting all the leaves. Let $(v_1,v_2,\dots,v_m)$ be the
spine of a caterpillar $T$. The vertex ordering of $T$ obtained by inserting
the leaves adjacent to each $v_i$ immediately after $v_i$ has  bandwidth at
most $\Delta(T)$. 

\citet{KKM-JAlg99} proved that every (connected) AT-free graph $G$ has a
spanning caterpillar subgraph $T$, and adjacent vertices in $G$ are at
distance at most four in $T$. Moreover, for any edge $vw\in E(G)$ with $v$ and
$w$ at distance four in $T$, both $v$ and $w$ are leaves of $T$. Consider the
above vertex ordering of $T$ to be a vertex ordering of $G$. The bandwidth is
at most $3\Delta(T)\leq 3\Delta(G)$. \end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Chordal Graphs}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

A \emph{chord} of a cycle $C$ is an edge not in $C$ connecting two vertices in
$C$. A graph is \emph{chordal} if every induced cycle on at least four vertices
has at least one chord. The following famous characterisation of chordal graphs
is due to \citet{Dirac61}, \citet{FG-PJM65}, and \citet{Rose-JMAA70}.

\begin{theorem}[\citep{Rose-JMAA70,Dirac61,FG-PJM65}]\thmlabel{Chordal}
The following are equivalent for a graph $G$:\\
\aaa\ $G$ is a chordal,\\
\bbb\ $G$ is the intersection graph of subtrees of a tree, and\\
\ccc\ $G$ has a vertex ordering $(v_1,v_2,\dots,v_n)$ such that,
\begin{equation}
\eqnlabel{Chordal}
\forall\,i<j<k,\;
v_iv_j\in E(G)\;\wedge\;v_iv_k\in E(G)\;\Rightarrow\;v_jv_k\in E(G)\enspace.
\end{equation}
\end{theorem}

A striking generalisation of \thmref{Chordal} for $k$-chordal graphs is given
by \citet{DKT-TCS97}. A vertex ordering satisfying \eqnref{Chordal} is called a
\emph{perfect elimination} vertex ordering. It is not possible to bound the
bandwidth of every chordal graph $G$ in terms of $\Delta(G)$. For example, the
bandwidth of the complete binary tree on $n$ vertices is $\approx n/\log n$
\citep{Smithline-DM95}.

%,GMO-CN90,OW-JCTB87,WangYao-AMAS95,Lam-AMAS98} for
%results on bandwidth of trees; in particular, bandwidth of $T$ is at most half
%the number of leaves in $T$.

\medskip A graph $G$ is a \emph{split graph} if $V(G)=K\cup I$, where $K$
induces a complete graph of $G$, and $I$ is an independent set of $G$.

\begin{theorem}\thmlabel{Split}
The following are equivalent for a graph $G$:\\
\aaa\ $G$ is a split graph,\\
\bbb\ $G$ is chordal and $\overline{G}$ is chordal,\\
\ccc\ $G$ has a vertex ordering $(v_1,v_2,\dots,v_n)$ simultaneously satisfying
\eqnref{Chordal} and
\begin{equation}
\eqnlabel{Split}
\forall\,i<j<k,\;
v_iv_j\in E(G)\;\Rightarrow\;v_jv_k\in E(G)\;\vee\;v_iv_k\in E(G)\enspace,
\end{equation}
\ddd\ $G$ has a vertex ordering $(v_1,v_2,\dots,v_n)$ such that,
\begin{equation}
\eqnlabel{SimpleSplit}
\forall\,i<j<k,\;
v_iv_j\in E(G)\;\Rightarrow\;v_jv_k\in E(G)\enspace.
\end{equation}
\end{theorem}

\begin{proof}
\citet{FH77} proved that \aaa\ and \bbb\ are equivalent.

Observe that \ddd\ implies \ccc\ trivially. 
We now prove that \aaa\ implies \ddd. 
Let $G$ be a split graph with $V(G)=K\cup I$, where $K$ induces a complete
subgraph and $I$ is an independent set. Let $m=|I|$.
Consider a vertex ordering $(v_1,v_2,\dots,v_n)$ of $G$ where
$I=\{v_1,v_2,\dots,v_m\}$ and $K=\{v_{m+1},v_{m+2},\dots,v_n\}$. 
Suppose that $1\leq i<j<k\leq n$ and $v_iv_j\in E(G)$. 
There is no edge with both endpoints in $I$.
Thus $j\geq m+1$, and both $v_j,v_k\in K$.
Hence $v_jv_k\in E(G)$, and 
$(v_1,v_2,\dots,v_n)$ satisfies \eqnref{SimpleSplit}.

It remains to prove that \ccc\ implies \bbb.
Let $(v_1,v_2,\dots,v_n)$ be a vertex ordering of a graph $G$ 
satisfying \eqnref{Chordal} and \eqnref{Split}.
By \thmref{Chordal}, $G$ is chordal.
Equation \eqnref{Split} is equivalent to:
\begin{equation}
\eqnlabel{SplitDual}
\forall\,i<j<k,\;
v_jv_k\in E(\overline{G})\;\wedge\;v_iv_k\in E(\overline{G})
\;\Rightarrow\;
v_iv_j\in E(\overline{G})
\enspace.
\end{equation}
That is, $(v_n,v_{n-1},\dots,v_1)$ is a perfect elimination vertex ordering of
$\overline{G}$. By \thmref{Chordal}, $\overline{G}$ is chordal.
\end{proof}

\begin{lemma}
\lemlabel{SplitBandwidth}
Every split graph $G$ has bandwidth at most $\Delta(G)\,(\Delta(G)+2)$. For all
$\Delta\geq2$ there is a split graph $G$ with $\Delta(G)=\Delta$, and $G$
has bandwidth at least $\Delta(G)^2/12$.
\end{lemma}

\begin{proof} First we prove the upper bound. 
Let $G$ be a split graph with $V(G)=K\cup I$, where $K$
induces a complete subgraph, and $I$ is an independent set. 
The result is trivial if $K=\emptyset$. 
Now assume that $K\ne\emptyset$. 
Let $I_0$ be the set of isolated vertices in $G$.
Consider a vertex ordering $\pi$ 
in which the vertices in $I_0$ precede all other vertices.
Let $I_1=I\setminus I_0$.
Regardless of the order of $I_1\cup K$, the bandwidth of $\pi$ is at most
$|I_1|+|K|-1$. Thus it suffices to prove that
$|I_1|+|K|\leq\Delta(G)\,(\Delta(G)+2)+1$.

If $I_1=\emptyset$ then $\pi$ has bandwidth $\Delta(G)$. 
Now assume that $I_1\ne\emptyset$. 
Let $a$ be the average degree of vertices in $I_1$. 
Thus $1\leq a\leq |K|$. 
For each vertex $v\in K$, let  $b_v=\deg(v)-|K|+1$. 
That is, $b_v$ is the number of edges between $v$ and $I_1$. 
Let $b=\sum_{v\in K}b_v/|K|$. Thus $a|I_1|=b|K|$, which
implies that 
\begin{equation*}
|I_1|+|K|
\;=\;
\frac{b|K|}{a}+|K|
\;=\;
\frac{(b+a)|K|}{a}\enspace.
\end{equation*}
Now $\Delta(G)$ is at least the average degree of the vertices in $K$.
That is, $\Delta(G)\geq |K|-1+b$. Hence
\begin{equation*}
\frac{|I_1|+|K|}{(\Delta(G)+1)^2}
\;\leq\;
\frac{(b+a)|K|}{a(|K|+b)^2}\enspace.
\end{equation*}
Since $a\leq |K|$,
\begin{equation*}
\frac{|I_1|+|K|}{(\Delta(G)+1)^2}
\;\leq\;
\frac{|K|}{a(|K|+b)}
\enspace.
\end{equation*}
Since $a\geq1$ and $b\geq0$, 
\begin{equation*}
|I_1|+|K|
\;\leq\;
(\Delta(G)+1)^2
\;=\;\Delta(G)\,(\Delta(G)+2)+1\enspace,
\end{equation*}
as required.

Now we prove the lower bound. 
Given $\Delta$, let $n=\floor{\Delta/2}$. 
Let $G$ be the split graph with $V(G)=K\cup I$, where 
$K$ is a complete graph on $n$ vertices, and
$I$ is an independent set on $n(\Delta-n+1)$ vertices, 
such that every vertex in $K$ is adjacent to $\Delta-n+1$ vertices in $I$, 
and every vertex in $I$ is adjacent to exactly one vertex in $K$.
Clearly $G$ has diameter 3, maximum degree $\Delta$, 
and $n+n(\Delta-n+1)=n(\Delta+n-2)$ vertices. 
It is easily seen that every connected graph with $n'$ vertices and 
diameter $d'$ has bandwidth at least
$(n'-1)/d'$ \citep{CCDG-Bandwidth-JGT82}. 
Thus $G$ has bandwidth at least 
\begin{equation*}
\frac{1}{3}\bracket{ n(\Delta-n+2)-1 }
\;=\;
\frac{1}{3}\bracket{ \FLOOR{\frac{\Delta}{2}}\CEIL{\frac{\Delta+2}{2}}-1 }
\;\geq\;
\frac{\Delta^2}{12}\enspace.
\end{equation*}
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\subsection*{Acknowledgements}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bibliographystyle{myBibliographyStyle}
\bibliography{myBibliography,myConferences}

\end{document}

myCommands.tex
\DeclareFontShape{OT1}{cmr}{b}{sc}
{<5><6><7><8><9><10><12><10.95><14.4><17.28><20.74><24.88>cmbcsc10}{}
\DeclareFontShape{OT1}{cmr}{bx}{sc}
{<5><6><7><8><9><10><12><10.95><14.4><17.28><20.74><24.88>cmbcsc10}{}

\DeclareFontShape{OT1}{cmr}{b}{tt}
{<5><6><7><8><9><10><12><10.95><14.4><17.28><20.74><24.88>cmbtt10}{}
\DeclareFontShape{OT1}{cmr}{bx}{tt}
{<5><6><7><8><9><10><12><10.95><14.4><17.28><20.74><24.88>cmbtt10}{}

%%%%%%%%%%%%%%%%

\newcommand{\myKeywords}[1]{\medskip\noindent \hspace*{8mm}
\begin{minipage}[t]{\textwidth-16mm} \textbf{Keywords}: \small #1
\end{minipage}}

\newcommand{\FancyFootnotes}{\renewcommand{\thefootnote}{\fnsymbol{footnote}}}
\newcommand{\FancyFootnotesOff}{\renewcommand{\thefootnote}{\arabic{footnote}}}

\newcommand{\YES}{\textup{\textsf{YES}}}
\newcommand{\NO}{\textup{\textsf{NO}}}

\newcommand{\Prob}[1]{\ensuremath{\textbf{\textup{P}}#1}}
\newcommand{\PROB}[1]{\ensuremath{\textbf{P}\left[#1\right]}}

\newcommand{\e}{\ensuremath{\boldsymbol{e}}}

\newcommand{\Case}[3]{\medskip\boldmath\textbf{Case #1 --- #2}\unboldmath#3: }
\newcommand{\case}[2]{\boldmath\textbf{Case #1. #2:}\unboldmath}
\newcommand{\BoldSimpleCase}[2]{\boldmath\textbf{Case #1. #2:}\unboldmath}

\newcommand{\raised}[1]{\footnotesize\raisebox{1ex}{#1}\normalsize}
\newcommand{\lowered}[1]{\footnotesize\raisebox{-1ex}{#1}\normalsize}

\newcommand{\paran}[1]{\textup{(}#1\textup{)}}

\newcommand{\Succ}[2][]{\ensuremath{\protect\textup{succ}_{#1}(#2)}}
\newcommand{\Pred}[2][]{\ensuremath{\protect\textup{pred}_{#1}(#2)}}
\newcommand{\set}[1]{\ensuremath{\protect\{#1\}}}
\newcommand{\SET}[1]{\ensuremath{\protect\left\{#1\right\}}}
\newcommand{\maxm}[1]{\ensuremath{\protect\max\set{#1}}}
\newcommand{\MAXM}[1]{\ensuremath{\protect\max\SET{#1}}}
\newcommand{\minm}[1]{\ensuremath{\protect\min\set{#1}}}
\newcommand{\MINM}[1]{\ensuremath{\protect\min\SET{#1}}}
\newcommand{\bracket}[1]{\ensuremath{\protect\left(#1\right)}}
\newcommand{\bb}[1]{\ensuremath{\protect\Big(#1\Big)}}
\renewcommand{\angle}[1]{\ensuremath{\protect\langle#1\rangle}}
\newcommand{\ABS}[1]{\ensuremath{\protect\left|#1\right|}}
\newcommand{\CARD}[1]{\ensuremath{\protect\left|#1\right|}}
\newcommand{\abs}[1]{\ensuremath{\protect|#1|}}
\newcommand{\card}[1]{\ensuremath{\protect|#1|}}
\newcommand{\ceil}[1]{\ensuremath{\protect\lceil#1\rceil}}
\newcommand{\ceilceil}[1]{\ensuremath{\protect\lceil\lceil#1\rceil\rceil}}
\newcommand{\CEILCEIL}[1]{\ensuremath{\protect\left\lceil\left\lceil#1\right\rceil\right\rceil}}
\newcommand{\CEIL}[1]{\ensuremath{\protect\left\lceil#1\right\rceil}}
\newcommand{\FLOOR}[1]{\ensuremath{\protect\left\lfloor#1\right\rfloor}}
\newcommand{\floor}[1]{\ensuremath{\protect\lfloor#1\rfloor}}

\newcommand{\eqdef}[0]{\ensuremath{\substack{\text{ \emph{def} }\\=}}}
\newcommand{\HALF}{\ensuremath{\protect\dfrac{1}{2}}}
\newcommand{\half}{\ensuremath{\protect\tfrac{1}{2}}}
\newcommand{\eighth}{\ensuremath{\protect\tfrac{1}{8}}}
\newcommand{\EIGHTH}{\ensuremath{\protect\dfrac{1}{8}}}
\newcommand{\threeeighths}{\ensuremath{\protect\tfrac{3}{8}}}
\newcommand{\THREEEIGHTHS}{\ensuremath{\protect\dfrac{3}{8}}}
\newcommand{\QUART}{\ensuremath{\protect\dfrac{1}{4}}}
\newcommand{\quart}{\ensuremath{\protect\tfrac{1}{4}}}
\newcommand{\QUARTER}{\ensuremath{\protect\dfrac{1}{4}}}
\newcommand{\quarter}{\ensuremath{\protect\tfrac{1}{4}}}
\newcommand{\SIXTH}{\ensuremath{\protect\dfrac{1}{6}}}
\newcommand{\sixth}{\ensuremath{\protect\tfrac{1}{6}}}
\newcommand{\THIRD}{\ensuremath{\protect\dfrac{1}{3}}}
\newcommand{\third}{\ensuremath{\protect\tfrac{1}{3}}}
\newcommand{\THREEQUARTS}{\ensuremath{\protect\dfrac{3}{4}}}
\newcommand{\threequarts}{\ensuremath{\protect\tfrac{3}{4}}}
\newcommand{\TWOTHIRDS}{\ensuremath{\protect\dfrac{2}{3}}}
\newcommand{\twothirds}{\ensuremath{\protect\tfrac{2}{3}}}

%\newcommand{\outdeg}[1]{\mbox{(out)deg}\bracket{#1}}
%\newcommand{\outdeg}[2][]{\ensuremath{\protect\textup{deg}_{#1}(#2)}} %^+
%\newcommand{\indeg}[2][]{\ensuremath{\protect\textup{deg}^-_{#1}(#2)}}
\newcommand{\maxoutdeg}[1]{\ensuremath{\protect\Delta^+(#1)}}
\newcommand{\maxindeg}[1]{\ensuremath{\protect\Delta^-(#1)}}

\newcommand{\ontop}[2]{\protect\substack{#1\\#2}}
\newcommand{\ontoptop}[3]{\protect\substack{#1\\#2\\#3}}
\newcommand{\range}[3]{\protect\left\{#1,#2,\ldots,#3\right\}}

\newcommand{\etal}{~\emph{et~al.}~}

\newcommand{\arc}[1]{\ensuremath{\protect\overrightarrow{#1}}}
\newcommand{\ArcGraph}[1]{\overleftrightarrow{#1}}

\newcommand{\YDelta}{\protect{Y}\Delta}
\newcommand{\DeltaY}{\protect\Delta{Y}}

\newcommand{\leftbrace}[1]{\left\{#1\right.}
\newcommand{\rightbrace}[1]{\left.#1\right\}}

\newcommand{\lb}[1]{\ensuremath{\protect\Omega(#1)}}
\newcommand{\tb}[1]{\ensuremath{\protect\Theta(#1)}}
\newcommand{\ub}[1]{\ensuremath{\protect\mathcal{O}(#1)}}

%\newcommand{\LB}[1]{\ensuremath{\protect\Omega\!\left(#1\right)}}
%\newcommand{\TB}[1]{\ensuremath{\protect\Theta\!\left(#1\right)}}
%\newcommand{\UB}[1]{\ensuremath{\protect\mathcal{O}\!\left(#1\right)}}

\newcommand{\oh}[1]{\ensuremath{\protect o\!\left(#1\right)}}
\newcommand{\Oh}[1]{\ensuremath{\protect\mathcal{O}(#1)}}
\newcommand{\bigOh}[1]{\ensuremath{\protect\mathcal{O}\!\big(#1\big)}}
\newcommand{\BigOh}[1]{\ensuremath{\protect\mathcal{O}\!\Big(#1\Big)}}
\newcommand{\OH}[1]{\ensuremath{\protect\mathcal{O}\!\left(#1\right)}}

\newcommand{\plane}[1]{\mbox{\ensuremath{(#1)}-plane}}


\newcommand{\EndProof}[1]{
\begin{minipage}[b]{\textwidth-1cm}
#1
\end{minipage}\hfill\qed
\vspace*{1ex}
\renewcommand{\qed}{}
}

\newcommand{\contradiction}
{\raisebox{0.7ex}{
\hspace*{1mm}
\pspicture(0,0)
\psset{unit=4mm}
\SpecialCoor
\pscircle(0;0){1}
\pscircle*(0.5;45){0.15}
\pscircle*(0.5;135){0.15}
\psarc(0.5;270){0.3}{10}{170}
\endpspicture}
\hspace*{0mm}}

\newcommand{\Figure}[4][htb]{
\begin{figure}[#1]
	\vspace*{1ex}
	\begin{center}#3\end{center}
	\vspace*{-3ex}
	\caption{\figlabel{#2}#4}
\end{figure}
}

\newcommand{\OneColumnFigure}[4]{
\begin{figure*}[#1]
	\vspace*{1ex}
	\begin{center}#3\end{center}
	\vspace*{-3ex}
	\caption{\figlabel{#2}#4}
\end{figure*}
}

%\newcommand{\claim}[2]{
%\noindent\textbf{Claim}: \emph{1}
%\begin{proof}
%2
%\end{proof}}

\newcommand{\Settings}[5]{
% 1: Spacing 
% 2: LRMargin
% 3: TBMargin
% 4: Head Sep
% 5: foot skip

% controls line spacing
\renewcommand{\baselinestretch}{#1}
\setlength{\footnotesep}{\baselinestretch\footnotesep}

% the size of margin notes
\setlength{\marginparwidth}{0mm}
\setlength{\marginparsep}{0mm}
\setlength{\marginparpush}{0mm}

%  These define the size of actual margins around the text
\newlength{\LRmargin}
\setlength{\LRmargin}{#2}
\newlength{\TBmargin}
\setlength{\TBmargin}{#3}

%  Now adjust page length parameters to reflect desired margins
\setlength{\voffset}{-1in}           % cancels default printer margin
\setlength{\hoffset}{-1in}           % cancels default printer margin

\setlength{\headsep}{#4}
\setlength{\footskip}{#5}

\setlength{\oddsidemargin}{\LRmargin}
\setlength{\evensidemargin}{\LRmargin}
\setlength{\topmargin}{\TBmargin}

\setlength{\textheight}{\paperheight}
\addtolength{\textheight}{-1in}			% default printer margin
\addtolength{\textheight}{-1.0\voffset}
\addtolength{\textheight}{-2.0\TBmargin}	% top and bottom
\addtolength{\textheight}{-1.0\headheight}
\addtolength{\textheight}{-1.0\headsep}
\addtolength{\textheight}{-1.0\footskip}

\setlength{\textwidth}{\paperwidth}
\addtolength{\textwidth}{-1.0in}		% default printer margin
\addtolength{\textwidth}{-1.0\hoffset}
\addtolength{\textwidth}{-2.0\LRmargin}		% left and right margin
}

\newcommand{\NewSettings}[6]{
% 1: Spacing 
% 2: LeftMargin
% 3: RightMargin
% 4: TBMargin
% 5: Head Sep
% 6: foot skip

% contols line spacing
\renewcommand{\baselinestretch}{#1}
\setlength{\footnotesep}{\baselinestretch\footnotesep}

% the size of margin notes
\setlength{\marginparwidth}{0mm}
\setlength{\marginparsep}{0mm}
\setlength{\marginparpush}{0mm}

%  These define the size of actual margins around the text
\newlength{\Lmargin}
\setlength{\Lmargin}{#2}
\newlength{\Rmargin}
\setlength{\Rmargin}{#3}
\newlength{\TBmargin}
\setlength{\TBmargin}{#4}

%  Now adjust page length parameters to reflect desired margins
\setlength{\voffset}{-1in}           % cancels default printer margin
\setlength{\hoffset}{-1in}           % cancels default printer margin

\setlength{\headsep}{#5}
\setlength{\footskip}{#6}

\setlength{\oddsidemargin}{\Lmargin}
\setlength{\evensidemargin}{\Lmargin}
\setlength{\topmargin}{\TBmargin}

\setlength{\textheight}{\paperheight}
\addtolength{\textheight}{-1in}			% default printer margin
\addtolength{\textheight}{-1.0\voffset}
\addtolength{\textheight}{-2.0\TBmargin}	% top and bottom
\addtolength{\textheight}{-1.0\headheight}
\addtolength{\textheight}{-1.0\headsep}
\addtolength{\textheight}{-1.0\footskip}

\setlength{\textwidth}{\paperwidth}
\addtolength{\textwidth}{-1.0in}		% default printer margin
\addtolength{\textwidth}{-1.0\hoffset}
\addtolength{\textwidth}{-1.0\Lmargin}		% left and right margin
\addtolength{\textwidth}{-1.0\Rmargin}		% left and right margin
}

\newcommand{\FullSettings}[7]{
% 1: Spacing 
% 2: LeftMargin
% 3: RightMargin
% 4: TopMargin
% 5: BottomMargin
% 6: Head Sep
% 7: foot skip

% contols line spacing
\renewcommand{\baselinestretch}{#1}
\setlength{\footnotesep}{\baselinestretch\footnotesep}

% the size of margin notes
\setlength{\marginparwidth}{0mm}
\setlength{\marginparsep}{0mm}
\setlength{\marginparpush}{0mm}

%  These define the size of actual margins around the text
\newlength{\Lmargin}
\setlength{\Lmargin}{#2}
\newlength{\Rmargin}
\setlength{\Rmargin}{#3}
\newlength{\Tmargin}
\setlength{\Tmargin}{#4}
\newlength{\Bmargin}
\setlength{\Bmargin}{#5}

%  Now adjust page length parameters to reflect desired margins
\setlength{\voffset}{-1in}           % cancels default printer margin
\setlength{\hoffset}{-1in}           % cancels default printer margin

\setlength{\headsep}{#6}
\setlength{\footskip}{#7}

\setlength{\oddsidemargin}{\Lmargin}
\setlength{\evensidemargin}{\Lmargin}
\setlength{\topmargin}{\Tmargin}

\setlength{\textheight}{\paperheight}
\addtolength{\textheight}{-1in}			% default printer margin
\addtolength{\textheight}{-1.0\voffset}
\addtolength{\textheight}{-1.0\Tmargin}
\addtolength{\textheight}{-1.0\Bmargin}
\addtolength{\textheight}{-1.0\headheight}
\addtolength{\textheight}{-1.0\headsep}
\addtolength{\textheight}{-1.0\footskip}

\setlength{\textwidth}{\paperwidth}
\addtolength{\textwidth}{-1.0in}		% default printer margin
\addtolength{\textwidth}{-1.0\hoffset}
\addtolength{\textwidth}{-1.0\Lmargin}
\addtolength{\textwidth}{-1.0\Rmargin}
}

\newlength{\marginboxwidth}

\newcommand{\OldComment}[1]{
\setlength{\marginboxwidth}{\evensidemargin}
\addtolength{\marginboxwidth}{-2em}
\marginpar{\hspace*{1em}\fbox{\parbox{\marginboxwidth}{\setlength{\baselineskip}{3ex}#1}}}}

\usepackage{pifont}

\newcommand{\Comment}[1]
{
\ding{43}
\setlength{\marginboxwidth}{\paperwidth}
\addtolength{\marginboxwidth}{-1.0\textwidth}
\addtolength{\marginboxwidth}{-1.0\evensidemargin}	% Lmargin
\addtolength{\marginboxwidth}{-15mm}
\marginpar{\hspace*{1em}\fbox{\parbox{\marginboxwidth}{\setlength{\baselineskip}{3ex}#1}}}
}

\newcommand{\NewComment}[2][2cm]
{
\marginpar{\hspace*{1em}\fbox{\parbox{#1}{\setlength{\baselineskip}{3ex}#2}}}
}


\newcommand{\COMMENT}[1]{\medskip\noindent\framebox{\parbox{\textwidth-2mm}{#1}}\medskip}


myLabels.tex
\newcommand{\factref}[1]{Fact~\ref{fact:#1}}
\newcommand{\obsref}[1]{Observation~\ref{obs:#1}}
\newcommand{\twoobsref}[2]{Observations~\ref{obs:#1} and \ref{obs:#2}}
\newcommand{\twothmref}[2]{Theorems~\ref{thm:#1} and \ref{thm:#2}}
\newcommand{\lemref}[1]{Lemma~\ref{lem:#1}}
\newcommand{\twofigref}[2]{Figures~\ref{fig:#1} and \ref{fig:#2}}
\newcommand{\twolemref}[2]{Lemmata~\ref{lem:#1} and \ref{lem:#2}}
\newcommand{\threelemref}[3]{Lemmata~\ref{lem:#1}, \ref{lem:#2} and \ref{lem:#3}}
\newcommand{\threethmref}[3]{Theorems~\ref{thm:#1}, \ref{thm:#2} and \ref{thm:#3}}
\newcommand{\thmref}[1]{Theorem~\ref{thm:#1}}
\newcommand{\twoFigref}[2]{Figures~\ref{fig:#1} and \ref{fig:#2}}
\newcommand{\Figref}[1]{Figure~\ref{fig:#1}}
%\newcommand{\figref}[1]{Fig.~\ref{fig:#1}}
\newcommand{\figsref}[1]{Figures~\ref{fig:#1}}
\newcommand{\figref}[1]{Figure~\ref{fig:#1}}
\newcommand{\secref}[1]{Section~\ref{sec:#1}}
\newcommand{\twosecref}[2]{Sections~\ref{sec:#1} and \ref{sec:#2}}
\newcommand{\threesecref}[3]{Sections~\ref{sec:#1}, \ref{sec:#2} and \ref{sec:#3}}
\newcommand{\manysecref}[2]{Sections~\ref{sec:#1}--\ref{sec:#2}}
\newcommand{\appref}[1]{Appendix~\ref{app:#1}}
\newcommand{\twocorref}[2]{Corollaries~\ref{cor:#1} and \ref{cor:#2}}
\newcommand{\corref}[1]{Corollary~\ref{cor:#1}}
\newcommand{\twotabref}[2]{Tables~\ref{tab:#1} and \ref{tab:#2}}
\newcommand{\tabref}[1]{Table~\ref{tab:#1}}
\newcommand{\algref}[1]{Algorithm~\ref{alg:#1}}
\newcommand{\Eqnref}[1]{Eq.~\eqref{eqn:#1}}
\newcommand{\eqnref}[1]{\eqref{eqn:#1}}
\newcommand{\stepref}[1]{Step~\ref{it:#1}}    
\newcommand{\itemref}[1]{\ref{it:#1}}    
\newcommand{\stepsref}[2]{\mbox{Steps~\ref{it:#1}--\ref{it:#2}}}
\newcommand{\conjref}[1]{Conjecture~\ref{con:#1}}    
\newcommand{\openref}[1]{Open Problem~\ref{open:#1}}    

\newcommand{\openlabel}[1]{\label{open:#1}}
\newcommand{\factlabel}[1]{\label{fact:#1}}
\newcommand{\itemlabel}[1]{\label{it:#1}}
\newcommand{\itlabel}[1]{\label{it:#1}}
\newcommand{\seclabel}[1]{\label{sec:#1}}
\newcommand{\figlabel}[1]{\label{fig:#1}}
\newcommand{\tablabel}[1]{\label{tab:#1}}
\newcommand{\thmlabel}[1]{\label{thm:#1}}
\newcommand{\lemlabel}[1]{\label{lem:#1}}
\newcommand{\obslabel}[1]{\label{obs:#1}}
\newcommand{\applabel}[1]{\label{app:#1}}
\newcommand{\corlabel}[1]{\label{cor:#1}}
\newcommand{\eqnlabel}[1]{\label{eqn:#1}}
\newcommand{\alglabel}[1]{\label{alg:#1}}
\newcommand{\conjlabel}[1]{\label{con:#1}}

\newcommand{\mySection}[2]{\section{#1}\seclabel{#2}}
\newcommand{\mySubSection}[2]{\subsection{#1}\seclabel{#2}}


myTheorems.tex
\usepackage{amsthm}

\theoremstyle{plain}
\newtheorem{fact}{Fact}
\newtheorem{observation}{Observation}
\newtheorem{theorem}{Theorem}
\newtheorem{algorithm}{Algorithm}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}

\theoremstyle{definition}
\newtheorem{conjecture}{Conjecture}
\newtheorem{definition}{Definition}
\newtheorem{open}{Open Problem}
\newtheorem{problem}{Open Problem}
\newtheorem{question}{Question}
\newtheorem{note}{Note}
\newtheorem{task}{Task}
\newtheorem{idea}{Idea}

\newcommand{\myCorollary}[3][]{\begin{corollary}\hspace*{-0.2em}\textup{\textbf{#1}}\corlabel{#2}\;\protect#3\end{corollary}}
\newcommand{\myLemma}[3][]{\begin{lemma}\hspace*{-0.2em}\textup{\textbf{#1}}\lemlabel{#2}\;\protect#3\end{lemma}}
\newcommand{\myTheorem}[3][]{\begin{theorem}\hspace*{-0.2em}\textup{\textbf{#1}}\thmlabel{#2}\;#3\end{theorem}}
\newcommand{\myConjecture}[3][]{\begin{conjecture}\hspace*{-0.2em}\textup{\textbf{#1}}\conjlabel{#2}\;\protect#3\end{conjecture}}
\newcommand{\myOpen}[3][]{\begin{open}\hspace*{-0.2em}\textup{\textbf{#1}}\openlabel{#2}\;\protect#3\end{open}}


Wood-IntersectionGraphOrdering.bbl
\def\soft#1{\leavevmode\setbox0=\hbox{h}\dimen7=\ht0\advance \dimen7
  by-1ex\relax\if t#1\relax\rlap{\raise.6\dimen7
  \hbox{\kern.3ex\char'47}}#1\relax\else\if T#1\relax
  \rlap{\raise.5\dimen7\hbox{\kern1.3ex\char'47}}#1\relax \else\if
  d#1\relax\rlap{\raise.5\dimen7\hbox{\kern.9ex \char'47}}#1\relax\else\if
  D#1\relax\rlap{\raise.5\dimen7 \hbox{\kern1.4ex\char'47}}#1\relax\else\if
  l#1\relax \rlap{\raise.5\dimen7\hbox{\kern.4ex\char'47}}#1\relax \else\if
  L#1\relax\rlap{\raise.5\dimen7\hbox{\kern.7ex
  \char'47}}#1\relax\else\message{accent \string\soft \space #1 not
  defined!}#1\relax\fi\fi\fi\fi\fi\fi} \def\cprime{$'$}
\begin{thebibliography}{17}
\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi

\bibitem[{Baker \emph{et~al.}(1972)Baker, Fishburn, and
  Roberts}]{BFR-Networks72}
\textsc{K.~A. Baker, P.~C. Fishburn, and F.~S. Roberts}, Partial orders of
  dimension {$2$}. \emph{Networks}, \textbf{2}:11--28, 1972.

\bibitem[{Chinn \emph{et~al.}(1982)Chinn, Chv{\'a}talov{\'a}, Dewdney, and
  Gibbs}]{CCDG-Bandwidth-JGT82}
\textsc{P.~Z. Chinn, J.~Chv{\'a}talov{\'a}, A.~K. Dewdney, and N.~E. Gibbs},
  The bandwidth problem for graphs and matrices---a survey. \emph{J. Graph
  Theory}, \textbf{6(3)}:223--254, 1982.

\bibitem[{Corneil(2004)}]{Corneil-DAM04}
\textsc{D.~G. Corneil}, A simple 3-sweep {LBFS} algorithm for the recognition
  of unit interval graphs. \emph{Discrete Appled Math.}, \textbf{139}:371--379,
  2004.

\bibitem[{Dendris \emph{et~al.}(1997)Dendris, Kirousis, and
  Thilikos}]{DKT-TCS97}
\textsc{N.~D. Dendris, L.~M. Kirousis, and D.~M. Thilikos}, Fugitive-search
  games on graphs and related parameters. \emph{Theoret. Comput. Sci.},
  \textbf{172(1-2)}:233--254, 1997.

\bibitem[{Dirac(1961)}]{Dirac61}
\textsc{G.~A. Dirac}, On rigid circuit graphs. \emph{Abh. Math. Sem. Univ.
  Hamburg}, \textbf{25}:71--76, 1961.

\bibitem[{Dushnik and Miller(1941)}]{DushnikMiller41}
\textsc{B.~Dushnik and E.~W. Miller}, Partially ordered sets. \emph{Amer. J.
  Math.}, \textbf{63}:600--610, 1941.

\bibitem[{F\"{o}ldes and Hammer(1977)}]{FH77}
\textsc{S.~F\"{o}ldes and P.~L. Hammer}, Split graphs. In \emph{Proc. 8th
  Southeastern Conference on Combinatorics, Graph Theory and Computing},
  vol.~19 of \emph{Congressus Numerantium}, pp. 311--315, Utilitas Math., 1977.

\bibitem[{Fomin and Golovach(2003)}]{FominGolovach-DAM03}
\textsc{F.~V. Fomin and P.~A. Golovach}, Interval degree and bandwidth of a
  graph. \emph{Discrete Appl. Math.}, \textbf{129(2-3)}:345--359, 2003.

\bibitem[{Fulkerson and Gross(1965)}]{FG-PJM65}
\textsc{D.~R. Fulkerson and O.~A. Gross}, Incidence matrices and interval
  graphs. \emph{Pacific J. Math.}, \textbf{15}:835--855, 1965.

\bibitem[{Gilmore and Hoffman(1964)}]{GilmoreHoffman-CJM64}
\textsc{P.~C. Gilmore and A.~J. Hoffman}, A characterization of comparability
  graphs and of interval graphs. \emph{Canad. J. Math.}, \textbf{16}:539--548,
  1964.

\bibitem[{Golumbic \emph{et~al.}(1983)Golumbic, Rotem, and Urrutia}]{GRU-DM83}
\textsc{M.~C. Golumbic, D.~Rotem, and J.~Urrutia}, Comparability graphs and
  intersection graphs. \emph{Discrete Math.}, \textbf{43}:37--46, 1983.

\bibitem[{Kaplan and Shamir(1996)}]{KaplanShamir-SJC96}
\textsc{H.~Kaplan and R.~Shamir}, Pathwidth, bandwidth, and completion problems
  to proper interval graphs with small cliques. \emph{SIAM J. Comput.},
  \textbf{25(3)}:540--561, 1996.

\bibitem[{Kloks \emph{et~al.}(1999)Kloks, Kratsch, and M{\"u}ller}]{KKM-JAlg99}
\textsc{T.~Kloks, D.~Kratsch, and H.~M{\"u}ller}, Approximating the bandwidth
  for asteroidal triple-free graphs. \emph{J. Algorithms},
  \textbf{32(1)}:41--57, 1999.

\bibitem[{Kratochv{\'{\i}}l \emph{et~al.}(1986)Kratochv{\'{\i}}l, Goljan, and
  Ku{\v{c}}era}]{KGK86}
\textsc{J.~Kratochv{\'{\i}}l, M.~Goljan, and P.~Ku{\v{c}}era}, String graphs.
  \emph{Rozpravy \v Ceskoslovensk\'e Akad. V\v ed \v Rada Mat. P\v r\'\i rod.
  V\v ed}, \textbf{96(3)}, 1986.

\bibitem[{Looges and Olariu(1993)}]{LoogesOlariu93}
\textsc{P.~J. Looges and S.~Olariu}, Optimal greedy algorithms for indifference
  graphs. \emph{Comput. Math. Appl.}, \textbf{25(7)}:15--25, 1993.

\bibitem[{Rose(1970)}]{Rose-JMAA70}
\textsc{D.~J. Rose}, Triangulated graphs and the elimination process. \emph{J.
  Math. Anal. Appl.}, \textbf{32}:597--609, 1970.

\bibitem[{Smithline(1995)}]{Smithline-DM95}
\textsc{L.~Smithline}, Bandwidth of the complete {$k$}-ary tree. \emph{Discrete
  Math.}, \textbf{142(1-3)}:203--212, 1995.

\end{thebibliography}
