Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Co-Bipartite Circular-Arc Graphs <s> A standard problem in combinatorial theory is to characterize structures which satisfy a certain property by providing a minimum list of forbidden substructures, for example, Kuratowski's well known characterization of planar graphs. In this paper, we establish connections between characterization problems for interval graphs, circular are graphs, comparability graphs, planar lattices, 0–1 matrices, interval orders, partially ordered sets with dimension at most two, partially ordered sets with interval dimension at most two, and related problems involving the representation of families of finite sets by points or intervals of the real line. We use these connections to determine the collection of all 3-irreducible posets. We are then able to determine the collection of all 3-interval irreducible posets of height one and the set of all forbidden subgraphs with clique covering number two in the characterization of circular are graphs. <s> BIB001 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Co-Bipartite Circular-Arc Graphs <s> In our first remark we observe a property of circular arcs which is similar to the Helly property and is helpful in describing all maximal cliques in circular arc graphs (as well as allowing us to genralize a result of Tucker). Our main result is a new simple characterization of circular arc graphs of clique covering number two. These graphs play a crucial role in recognition algorithms for circular arc graphs, and have been characterized by several authors. Specifically, we show that a graph with clique covering number two is a circular arc graph if and only if its edges can be coloured by two colours so that no induced four-cycle contains two opposite edges of the same colour. Our proof of the characterization depends on the ‘lexicographic method’ we have recently introduced. Both remarks could be useful in designing efficient algorithms for (maximum cliques in, respectively recognition of) circular arc graphs <s> BIB002
One of the main classes of CA graphs, in general, is that of co-bipartite CA graphs. There are some nice structural characterizations for this class. Besides, many of the algorithms formulated in Sections 3 and 4, for recognizing CA and PCA graphs, respectively, handle separately the case where the given graph is co-bipartite. The following property was employed in Tucker's algorithm for recognizing CA graphs, and afterwards in other algorithms for CA and PCA graphs. The above property has been generalized by Hell and Huang BIB002 , to the entire class of CA graphs. The first characterization of co-bipartite CA graphs is by Trotter and Moore BIB001 , which also described a forbidden subgraph characterization for the class. The following concept has been employed in characterizations of co-bipartite CA graphs. An edge-asteroid of a graph G is a set of edges e i , admiting a circular ordering e 0 , e 1 , . . . , e 2k , such that for any i = 0, 1, . . . , 2k, there is a path containing both e i , e i+1 , which avoids the neighbors of e i+k+1 . The following theorem is by Feder, Hell and Huang.