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, G=(V,E)G=(V,E) is a 2-tree if and only if G   is CO and G′=(V,E′)G′=(V,E′) is not CO whenever E   is a proper subset of E′E′.