UNLV Mathematical Sciences
2007-2008 Colloquium

Full Orientability of Graphs


Dr. Ko-Wei Lih
Insitute of Mathematics
Academica Sinica (Taiwan)


Abstract

Suppose that D is an acyclic orientation of a simple graph G. An arc of D is called dependent if its reversal creates a directed cycle. Let dmin(G) (dmax(G)) denote the minimum (maximum) of the number of dependent arcs over all acyclic orientations of G. We say that G is fully orientable if G has an acyclic orientation with exactly d dependent arcs for every d satisfying dmin(G) ≤ d ≤ dmax(G). In this talk, I will survey recent results on preservation of fully orientability when a fully orientable graph is extended by attaching new paths or cycles. Applications of these preservation theorems will also be discussed.