DIMACS TR: 2005-08
Cyclically Orientable Graphs
Author: Vladimir Gurvich
ABSTRACT
ABSTRACT: Graph $G$ is called cyclically orientable (CO) if it admits
an orientation in which every simple chordless cycle is cyclically
oriented. This family of graphs was introduced
by Barot, Geiss, and Zelevinsky in their paper ``Cluster algebras of
finite type and
positive symmetrizable matrices'', {\em J. London Math. Soc.} {\bf 73}
Part 3 (2006), 545-564.
The authors obtained several nice characterizations of CO-graphs,
being motivated primarily
by their applications in cluster algebras. Here we obtain several new
characterizations
that provide algorithms for recognizing CO-graphs and obtaining their
cyclic orientations in linear time. We show that CO-graphs are edge
maximal 2-trees; that is, $G = (V,E)$ is a 2-tree if and only if
$G$ is CO and $G' = (V,E')$ is not CO whenever $E$ is a proper subset
of $E'$.
Keywords: cluster algebra, graph, chromatic number, planar graph,
series-parallel graph,
cycle, chord, chordless cycle, orientation, cyclic orientation, 2-tree.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-08.pdf
DIMACS Home Page