Abstract. We introduce the class of strong cocomparability graphs, as the class of reflexive graphs whose adjacency matrix can be rearranged by a simultaneous row and column permutation to avoid the submatrix with rows 01,10, which we call Slash. We provide an ordering characterization, a forbidden structure characterization, and a polynomial-time certifying recognition algorithm for the class. These results complete the picture in which in addition to, or instead of, the [Formula: see text] matrix one forbids the [Formula: see text] matrix (which has rows 11,10). It is well known that in these two cases one obtains the class of interval graphs and the class of strongly chordal graphs, respectively. By complementation, we obtain the class of strong comparability graphs, whose adjacency matrix can be rearranged by a simultaneous row and column permutation to avoid the two-by-two identity submatrix. Thus our results give characterizations and algorithms for this class of irreflexive graphs as well. In other words, our results may be interpreted as solving the following problem: given a symmetric 0,1-matrix with 0-diagonal, can the rows and columns of be simultaneously permuted to avoid the two-by-two identity submatrix?

We unify two popular graph classes, strongly chordal graphs and chordal bigraphs, by introducing an umbrella class that contains both classes and maintains their essential properties. This is done by allowing loops at vertices. Considering loops often has little impact on a class of graphs; it however makes a big difference in this case. We call the new class \itstrongly chordal graphs with possible loops. When all vertices have loops, we recover the usual strongly chordal graphs; when all vertices are loopless, we obtain the usual chordal bigraphs. Moreover, there is a surprizing wealth of graphs in the new class that have loops at some vertices and not at others. These graphs also admit the elegant algorithms previously only applied in the extreme two cases. Formulated in the language of adjacency matrices, we study the class of symmetric 0, 1 matrices that admit a simultaneous row and column permutation avoiding the $\Gamma$ matrix $[ \begin{smallmatrix} 1 \ 1 \\ 1 \ 0 \end{smallmatrix}]$. We give ordering characterizations, matrix characterizations, and forbidden subgraph characterizations of the new class, and illustrate its usefulness by solving the minimum domination problem in this general context. This implies solutions of both the minimum dominating set in strongly chordal graphs and the minimum total dominating set in chordal bigraphs.

We propose bipartite analogues of comparability and cocomparability graphs. Surprisingly, the two classes coincide. We call these bipartite graphs cocomparability bigraphs. We characterize cocomparability bigraphs in terms of vertex orderings, forbidden substructures, and orientations of their complements. In particular, we prove that cocomparability bigraphs are precisely those bipartite graphs that do not have edge-asteroids; this is analogous to Gallai's structural characterization of cocomparability graphs by the absence of (vertex-) asteroids. Our characterizations imply a robust polynomial-time recognition algorithm for the class of cocomparability bigraphs. Finally, we also discuss a natural relation of cocomparability bigraphs to interval containment bigraphs, resembling a well-known relation of cocomparability graphs to interval graphs.

We unify several seemingly different graph and digraph classes under one umbrella. These classes are all, broadly speaking, different generalizations of interval graphs, and include, in addition to interval graphs, adjusted interval digraphs, complements of threshold tolerance graphs (known as co-TT graphs), bipartite interval containment graphs, bipartite co-circular arc graphs, and two-directional orthogonal ray bigraphs. (The last three classes coincide, but have been investigated in different contexts.) We show that all of the above classes are united by a common ordering characterization, the existence of a min ordering. However, because the presence or absence of reflexive relationships (loops) affects whether a graph or digraph has a min ordering, to obtain this result, we must define the graphs and digraphs to have those loops that are implied by their definitions. These have been largely ignored in previous work. We propose a common generalization of all these graph and digraph classes, namely signed-interval digraphs, characterized by the existence of a compact representation, a signed-interval model, which is a generalization of known representations of the graph classes. We show that the signed-interval digraphs are precisely those digraphs that are characterized by the existence of a min ordering when the loops implied by the model are considered part of the graph. We also offer an alternative geometric characterization of these digraphs. We show that co-TT graphs are the symmetric signed-interval digraphs, the adjusted interval digraphs are the reflexive signed-interval digraphs, and the interval graphs are the intersection of these two classes, namely, the reflexive and symmetric signed-interval digraphs. Similar results hold for bipartite interval containment graphs, bipartite co-circular arc graphs, and two-directional orthogonal ray bigraphs.

We unify several seemingly different graph and digraph classes under one umbrella. These classes are all broadly speaking different generalizations of interval graphs, and include, in addition to interval graphs, also adjusted interval digraphs, threshold graphs, complements of threshold tolerance graphs (known as `co-TT' graphs), bipartite interval containment graphs, bipartite co-circular arc graphs, and two-directional orthogonal ray graphs. (The last three classes coincide, but have been investigated in different contexts.) This common view is made possible by introducing loops. We also show that all the above classes are united by a common ordering characterization, the existence of a min ordering. We propose a common generalization of all these graph and digraph classes, namely signed-interval digraphs, and show that they are precisely the digraphs that are characterized by the existence of a min ordering. We also offer an alternative geometric characterization of these digraphs. For most of the above example graph and digraph classes, we show that they are exactly those signed-interval digraphs that satisfy a suitable natural restriction on the digraph, like having all loops, or having a symmetric edge-set, or being bipartite. (For instance co-TT graphs are precisely those signed-interval digraphs that have each edge symmetric.) We also offer some discussion of recognition algorithms and characterizations, saving the details for future papers.

A graph is polar if its vertex set can be partitioned into [Formula: see text] and [Formula: see text] in such a way that [Formula: see text] induces a complete multipartite graph and [Formula: see text] induces a disjoint union of cliques (i.e., the complement of a complete multipartite graph). Polar graphs naturally generalize several classes of graphs such as bipartite, cobipartite, and split graphs. The problem of recognizing polar graphs is NP-complete in general. However, it has been shown to be polynomial for several classes of graphs, including cographs and chordal graphs. In this paper, we study the problem of recognizing graphs whose line graphs are polar. It turns out that the core part of this problem lies in determining whether the edge set of a graph admits a partition [Formula: see text] so that [Formula: see text] induces a [Formula: see text]-free subgraph (i.e., a matching) and [Formula: see text] induces a [Formula: see text]-free subgraph. We give a structural characterization of such graphs. The characterization enables us to devise an [Formula: see text] time algorithm to solve the stated recognition problem.

Let H be a graph and $k \geq 3$. A near-unanimity function of arity k is a mapping g from the k-tuples over $V(H)$ to $V(H)$ such that $g(x_1, x_2, \dots, x_k)$ is adjacent to $g(x'_1, x'_2, \dots, x'_k)$ whenever $x_i x'_i \in E(H)$ for each $i = 1, 2, \dots, k$, and $g(x_1, x_2, \dots, x_k) = a$ whenever at least $k-1$ of the $x_i$'s equal a. Feder and Vardi proved that, if a graph H admits a near-unanimity function, then the homomorphism extension (or retraction) problem for H is polynomial time solvable. We focus on near-unanimity functions on reflexive graphs. The best understood are reflexive chordal graphs H: they always admit a near-unanimity function. We bound the arity of these functions in several ways related to the size of the largest clique and the leafage of H, and we show that these bounds are tight. In particular, it will follow that the arity is bounded by $n -\sqrt{n}+1$, where $n = |V(H)|$. We investigate substructures forbidden for reflexive graphs that admit a near-unanimity function. It will follow, for instance, that no reflexive cycle of length at least four admits a near-unanimity function of any arity. However, we exhibit nonchordal graphs which do admit near-unanimity functions. Finally, we characterize graphs which admit a conservative near-unanimity function. This characterization has been predicted by the results of Feder, Hell, and Huang. Specifically, those results imply that, if P $\neq$ NP, the graphs with conservative near-unanimity functions are precisely the so-called bi-arc graphs. We give a proof of this statement without assuming P $\neq$ NP.

Brooks proved that every connected graph other than a clique or odd cycle can be colored with $\Delta$ colors. Erdős, Rubin, and Taylor (and, independently, Vizing) generalized the theorem of Brooks to list colorings, describing all uncolorable connected graphs in which no vertex has a list smaller than its degree. Other authors have extended this to list T-colorings and their generalizations. We further extend it to model pair-list colorings. In addition to including all of the previous situations, pair-list colorings also generalize list homomorphisms (also known as list H-colorings). In the general context of pair-list colorings, we prove a Brooks-type theorem which extends many (but not all) of the existing results. Our result applies to both graphs and digraphs, with or without loops. We discuss several applications of the result, including a polynomial test for the existence of balanced list homomorphisms and retractions.

Recently, D. Corneil found a simple 3-sweep lexicographic breadth first search (LexBFS) algorithm for the recognition of proper interval graphs. We point out how to modify Corneil's algorithm to make it a certifying algorithm, and then describe a similar certifying 3-sweep LexBFS algorithm for the recognition of proper interval bigraphs. It follows from an earlier paper that the class of proper interval bigraphs is equal to the better known class of bipartite permutation graphs, and so we have a certifying algorithm for that class as well. All our algorithms run in time O(m+n), including the certification phase. The certificates of representability (the intervals) can be authenticated in time O(m+n). The certificates of nonrepresentability (the forbidden subgraphs) can be authenticated in time O(n).

We consider the problem of finding a strongly connected spanning subdigraph with the minimum number of arcs in a strongly connected digraph. This problem is NP-hard for general digraphs since it generalizes the Hamiltonian cycle problem. We show that the problem is polynomially solvable for quasi-transitive digraphs. We describe the minimum number of arcs in such a spanning subdigraph of a quasi-transitive digraph in terms of the path covering number. Our proofs are based on a number of results (some of which are new and interesting in their own right) on the structure of cycles and paths in quasi-transitive digraphs and in extended semicomplete digraphs. In particular, we give a new characterization of the longest cycle in an extended semicomplete digraph. Finally, we point out that our proofs imply that the MSSS problem is solvable in polynomial time for all digraphs that can be obtained from strong semicomplete digraphs on at least two vertices by replacing each vertex with a digraph belonging to a family of digraphs whose path covering number can be decided in polynomial time.

We introduce two new classes of graphs which we call convex-round, respectively concave-round graphs. Convex-round (concave-round) graphs are those graphs whose vertices can be circularly enumerated so that the (closed) neighborhood 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 class of concave-round graphs properly contains the class of proper circular arc graphs and, by a result of Tucker [ Pacific J. Math., 39 (1971), pp. 535--545], is properly contained in the class of general circular arc graphs. We point 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 edges of the graph in question). We show that the chromatic number of a graph which 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 clique, a maximum matching, and a Hamiltonian cycle (if one exists) for the class of convex-round graphs. Finally, we pose a number of open problems and conjectures concerning the structure and algorithmic properties of the two new classes and a related third class of graphs.

Our main result is a linear-time (that is, time $O(m + n)$) algorithm to recognize and represent proper circular-arc graphs. The best previous algorithm, due to A. Tucker, has time complexity $O(n^2 )$. We take advantage of the fact that (among connected graphs) proper circular-arc graphs are precisely the graphs orientable as local tournaments, and we use a new characterization of local tournaments. The algorithm depends on repeated representation of portions of the input graph as proper interval graphs. Thus we also find it useful to give a new linear-time algorithm to represent proper interval graphs. This latter algorithm also depends on an orientation characterization of proper interval graphs. It is conceptually simple and does not use complex data structures. As a byproduct of the correctness proof of the algorithm, we also obtain a new proof of a characterization of proper interval graphs by forbidden subgraphs.

We present an $O(n)$algorithm to find a maximum clique in a proper circular arc graph. We assume that the input graph is represented by a sorted simple family of circular arcs or by an equivalent representation. In Deng, Hell, and Huang [SIAM J. Comput., 25 (1996), pp. 390–403], we gave an $O(m + n)$ algorithm to find such a representation for a proper circular arc graph given by its adjacency lists. As an application we also give an $O(n)$ algorithm for q-coloring proper circular arc graphs for a fixed q. (Such an algorithm was first given by Teng and Tucker.) Finally we indicate how our algorithm can be modified to find a maximum weight clique in a weighted graph, also in time $O(n)$.