DIMACS TR: 2005-08

Cyclically Orientable Graphs

Author: Vladimir Gurvich


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