Convex-round and concave-round graphs

We introduce two new classes of graphs which we call convex-round, respecti vely concave-round graphs. Convex-round (concave-round) graphs are those gr aphs whose vertices can be circularly enumerated so that the (closed) neigh borhood of each vertex forms an interval in the enumeration. Hence the two classes transform into each other by taking complements. We show that both classes of graphs have nice structural properties. We observe that the clas s of concave-round graphs properly contains the class of proper circular ar c graphs and, by a result of Tucker [Pacific J. Math., 39 (1971), pp. 535-5 45] is properly contained in the class of general circular arc graphs. We p oint out that convex-round and concave-round graphs can be recognized in O( n + m) time (here n denotes the number of vertices and m the number of edge s of the graph in question). We show that the chromatic number of a graph w hich is convex-round (concave-round) can be found in time O(n + m) (O(n(2)) ). We describe optimal O(n + m) time algorithms for finding a maximum cliqu e, a maximum matching, and a Hamiltonian cycle (if one exists) for the clas s of convex-round graphs. Finally, we pose a number of open problems and co njectures concerning the structure and algorithmic properties of the two ne w classes and a related third class of graphs.