On cyclically orientable graphs

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 et al. [Cluster algebras of finite type and positive symmetrizable matrices, J. London Math. Soc. (3) 73 (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 the edge maximal CO-graphs are 2-trees; that is, image is a 2-tree if and only if G is CO and image is not CO whenever E is a proper subset of image.