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?

Given a digraph $G$, a set $X\subseteq V(G)$ is said to be absorbing set (resp. dominating set) if every vertex in the graph is either in $X$ or is an in-neighbour (resp. out-neighbour) of a vertex in $X$. A set $S\subseteq V(G)$ is said to be an independent set if no two vertices in $S$ are adjacent in $G$. A kernel (resp. solution) of $G$ is an independent and absorbing (resp. dominating) set in $G$. We explore the algorithmic complexity of these problems in the well known class of interval digraphs. A digraph $G$ is an interval digraph if a pair of intervals $(S_u,T_u)$ can be assigned to each vertex $u$ of $G$ such that $(u,v)\in E(G)$ if and only if $S_u\cap T_v\neq\emptyset$. Many different subclasses of interval digraphs have been defined and studied in the literature by restricting the kinds of pairs of intervals that can be assigned to the vertices. We observe that several of these classes, like interval catch digraphs, interval nest digraphs, adjusted interval digraphs and chronological interval digraphs, are subclasses of the more general class of reflexive interval digraphs -- which arise when we require that the two intervals assigned to a vertex have to intersect. We show that all the problems mentioned above are efficiently solvable, in most of the cases even linear-time solvable, in the class of reflexive interval digraphs, but are APX-hard on even the very restricted class of interval digraphs called point-point digraphs, where the two intervals assigned to each vertex are required to be degenerate, i.e. they consist of a single point each. The results we obtain improve and generalize several existing algorithms and structural results for subclasses of reflexive interval digraphs.

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.

A signed graph is a graph together with an assignment of signs to the edges. A closed walk in a signed graph is said to be positive (negative) if it has an even (odd) number of negative edges, counting repetition. Recognizing the signs of closed walks as one of the key structural properties of a signed graph, we define a homomorphism of a signed graph $(G,σ)$ to a signed graph $(H, π)$ to be a mapping of vertices and edges of $G$ to (respectively) vertices and edges of $H$ which preserves incidence, adjacency and the signs of closed walks. In this work we first give a characterization of the sets of closed walks in a graph $G$ that correspond to the set of negative walks in some signed graph on $G$. We also give an easy algorithm for the corresponding decision problem. After verifying the equivalence between this definition and earlier ones, we discuss the relation between homomorphisms of signed graphs and those of 2-edge-colored graphs. Next we provide some basic no-homomorphism lemmas. These lemmas lead to a general method of defining chromatic number which is discussed at length. Finally, we list a few problems that are the driving force behind the study of homomorphisms of signed graphs.

Hamiltonicity of graphs possessing symmetry has been a popular subject of research, with focus on vertex-transitive graphs, and in particular on Cayley graphs. In this paper, we consider the Hamiltonicity of another class of graphs with symmetry, namely covering graphs of trees. In particular, we study the problem for covering graphs of trees, where the tree is a voltage graph over a cyclic group. Batagelj and Pisanski were first to obtain such a result, in the special case when the voltage assignment is trivial; in that case, the covering graph is simply a Cartesian product of the tree and a cycle. We consider more complex voltage assignments, and extend the results of Batagelj and Pisanski in two different ways; in these cases the covering graphs cannot be expressed as products. We also provide a linear time algorithm to test whether a given assignment satisfies these conditions.

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.

The Dichotomy Conjecture for constraint satisfaction problems (CSPs) states that every CSP is in P or is NP-complete (Feder-Vardi, 1993). It has been verified for conservative problems (also known as list homomorphism problems) by A. Bulatov (2003). Egri et al. (SODA 2014) augmented this result by showing that for digraph templates H, every conservative CSP, denoted LHOM(H), is solvable in log space or is hard for NL. A conjecture of Larose and Tesson from 2007 forecasts that when LHOM(H) is in log space, then in fact, it falls in a small subclass of log space, the set of problems expressible in symmetric Data log. The present work verifies the conjecture for LHOM(H) (and, indeed, for the wider class of conservative CSPs with binary constraints), and by so doing sharpens the aforementioned dichotomy. A combinatorial characterization of symmetric Data log provides the language in which the algorithmic ideas of the paper, quite different from the ones in Egri et al., are formalized.

A circular-arc graph is the intersection graph of arcs of a circle. It is a well-studied graph model with numerous natural applications. A certifying algorithm is an algorithm that outputs a certificate, along with its answer (be it positive or negative), where the certificate can be used to easily justify the given answer. While the recognition of circular-arc graphs has been known to be polynomial since the 1980s, no polynomial-time certifying recognition algorithm is known to date, despite such algorithms being found for many subclasses of circular-arc graphs. This is largely due to the fact that a forbidden structure characterization of circular-arc graphs is not known, even though the problem has been intensely studied since the seminal work of Klee in the 1960s. In this contribution, we settle this problem. We present the first forbidden structure characterization of circular-arc graphs. Our obstruction has the form of mutually avoiding walks in the graph. It naturally extends a similar obstruction that characterizes interval graphs. As a consequence, we give the first polynomial-time certifying algorithm for the recognition of circular-arc graphs.

The Dichotomy Conjecture for constraint satisfaction problems (CSPs) states that every CSP is in P or is NP-complete (Feder-Vardi, 1993). It has been verified for conservative problems (also known as list homomorphism problems) by Bulatov (2003). We augment this result by showing that for digraph templates H, every conservative CSP, denoted LHOM(H), is solvable in logspace or is hard for NL. More precisely, we introduce a digraph structure we call a circular N, and prove the following dichotomy: if H contains no circular N then LHOM(H) admits a logspace algorithm, and otherwise LHOM(H) is hard for NL. Our algorithm operates by reducing the lists in a complex manner based on a novel decomposition of an auxiliary digraph, combined with repeated applications of Reingold's algorithm for undirected reachability (2005). We also prove an algebraic version of this dichotomy: the digraphs without a circular N are precisely those that admit a finite chain of conservative polymorphisms satisfying the Hagemann-Mitschke identities. This confirms a conjecture of Larose and Tesson (2007) for LHOM(H). Moreover, we show that the presence of a circular N can be decided in time polynomial in the size of H.

We describe a generating set for the variety of simple graphs that admit a $k$-ary near-unanimity (NU) polymorphism. The result follows from an analysis of NU polymorphisms of strongly bipartite digraphs, i.e., whose vertices are either a source or a sink. We show that the retraction problem for a strongly bipartite digraph ${\mathbb H}$ has finite duality if and only if ${\mathbb H}$ admits an NU polymorphism. This result allows the use of tree duals to generate the variety of digraphs admitting a $k$-NU polymorphism.

Finding a forbidden subgraph characterization of circular-arc graphs is a challenging open problem. Many partial results toward this goal have been proposed over the years, but a satisfactory answer has so far eluded us. In this paper, we suggest a new direction in this line of research. We propose a novel structural obstruction to circular-arc graphs---a blocking quadruple---and study its use in characterizing circular-arc graphs within chordal graphs. Notably, we observe that the absence of blocking quadruples unifies characterizations of various known chordal subclasses of circular-arc graphs found in the literature. To this end, we provide a forbidden induced subgraph characterization of chordal graphs without blocking quadruples and show that the absence of blocking quadruples exactly characterizes chordal circular-arc graphs of independence number 4 or less. Our proof uses an interesting geometric approach, constructing a circular-arc representation by traversing around a carefully chosen clique tree. In fact, we prove that this characterizes circular-arc representability of all chordal graphs.

We describe a generating set for the variety of reflexive graphs that admit a compatible $k$-ary near-unanimity (NU) operation. We further delineate a very simple subset that generates the variety of $j$-absolute retracts; in particular we show that the class of reflexive graphs with a 4-NU operation coincides with the class of 3-absolute retracts. Our results generalize and encompass several results on NU-graphs and absolute retracts.

We introduce a class of digraphs analogous to proper interval graphs and bigraphs. They are defined via a geometric representation by two inclusion-free families of intervals satisfying a certain monotonicity condition; hence we call them monotone proper interval digraphs. They admit a number of equivalent definitions, including an ordering characterization by so-called Min-Max orderings , and the existence of certain graph polymorphisms. Min-Max orderings arose in the study of minimum cost homomorphism problems: if $H$ admits a a Min-Max ordering (or a certain extension of Min-Max orderings), then the minimum cost homomorphism problem to $H$ is known to admit a polynomial time algorithm. We give a forbidden structure characterization of monotone proper interval digraphs, which implies a polynomial time recognition algorithm. This characterizes digraphs with a Min-Max ordering; we also similarly characterize digraphs with an extended Min-Max ordering. In a companion paper, we shall apply this latter characterization to derive a conjectured dichotomy classification for the minimum cost homomorphism problems---namely, we shall prove that the minimum cost homomorphism problem to a digraph that does not admit an extended Min-Max ordering is NP-complete.

The minimum cost homomorphism problem has arisen as a natural and useful optimization problem in the study of graph (and digraph) coloring and homomorphisms: it unifies a number of other well studied optimization problems. It was shown by Gutin, Rafiey, and Yeo that the minimum cost problem for homomorphisms to a digraph $H$ that admits a so-called extended Min-Max ordering is polynomial time solvable, and these authors conjectured that for all other digraphs $H$ the problem is NP-complete. In a companion paper, we gave a forbidden structure characterization of digraphs that admit extended Min-Max orderings. In this paper, we apply this characterization to prove Gutin's conjecture.

The Dichotomy Conjecture for Constraint Satisfaction Problems has been verified for conservative problems (or, equivalently, for list homomorphism problems) by Andrei Bulatov. An earlier case of this dichotomy, for list homomorphisms to undirected graphs, came with an elegant structural distinction between the tractable and intractable cases. Such structural characterization is absent in Bulatov's classification, and Bulatov asked whether one can be found. We provide an answer in the case of digraphs. In the process we give forbidden structure characterizations of the existence of certain polymorphisms relevant in Bulatov's dichotomy classification. The key concept we introduce is that of a digraph asteroidal triple (DAT). The dichotomy then takes the following form. If a digraph H has a DAT, then the list homomorphism problem for H is NP-complete; and a DAT-free digraph H has a polynomial time solvable list homomorphism problem. DAT-free digraphs can be recognized in polynomial time. It follows from our results that the list homomorphism problem for a DAT-free digraph H can be solved by a local consistency algorithm (of width (2,3)).

For a fixed graph H, let $\textsc{Ret}(H)$ denote the problem of deciding whether a given input graph is retractable to H. We classify the complexity of $\textsc{Ret}(H)$ when H is a graph (with loops allowed) where each connected component has at most one cycle, i.e., a pseudoforest. In particular, this result extends the known complexity classifications of $\textsc{Ret}(H)$ for reflexive and irreflexive cycles to general cycles. Our approach is based mainly on algebraic techniques from universal algebra that previously have been used for analyzing the complexity of constraint satisfaction problems.

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.

Feder and Vardi have conjectured that all constraint satisfaction problems to a fixed structure (constraint language) are polynomial or NP-complete. This so-called dichotomy conjecture remains open, although it has been proved in a number of special cases. Most recently, Bulatov has verified the conjecture for conservative structures, i.e., structures which contain all possible unary relations. We explore three different implications of Bulatov's result. First, the above dichotomy can be extended to so-called inclusive structures, corresponding to conservative constraint satisfaction problems in which each variable comes with its own domain. (This has also been independently observed by Bulatov.) We prove a more general version, extending the dichotomy to so-called three-inclusive structures, i.e., structures which contain, with any unary relation R, all unary relations $R'$ for subsets $R' \subseteq R$ with at most three elements. For the constraint satisfaction problems in this generalization we must restrict the instances to so-called 1-full structures, in which each variable is involved in a unary constraint. This leads to our second focus, which is on restrictions to more general kinds of "full" input structures. For any set W of positive integers, we consider a restriction to W-full input structures, i.e., structures in which, for each $w \in W$, any w variables are involved in a w-ary constraint. We identify a class of structures (the so-called W-set-full structures) for which the restriction to W-full input structures does not change the complexity of the constraint satisfaction problem, and hence the family of these restricted problems also exhibits dichotomy. The general family of three-inclusive constraint satisfaction problems restricted to W-full input structures contains examples which we cannot seem to prove either polynomial or NP-complete. Nevertheless, we are able to use our result on the dichotomy for three-inclusive constraint satisfaction problems, to deduce the fact that all three-inclusive constraint satisfaction problems restricted to W-full input structures are NP-complete or "quasi-polynomial" (of order $n^{O(\log n)}$). Our third focus deals with bounding the number of occurrences of a variable, which we call the degree. We conjecture that the complexity classification of three-inclusive constraint satisfaction problems extends to the case where all degrees are bounded by three. Using previous results, we are able to verify this conjecture in a number of special cases. Conservative, inclusive, and three-inclusive constraint satisfaction problems can be viewed as problems in which each variable is restricted to a "list" of allowed values. This point of view of lists is frequently encountered in the study of graph colorings, graph homomorphisms, and graph partitions. Our results presented here, in all three areas, were strongly motivated by these results on graphs.

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).

Abstract Broadcasting is an information dissemination process in which a message originating at one node of a communication network (modeled as an undirected graph) is sent to all other nodes by means of calls involving two nodes at a time, with each node participating in at most one call at any time. We are interested in efficient broadcasting in a class of cubic graphs known as generalized chordal rings. These graphs have been found useful for having a small diameter D, among graphs with a given number of vertices and maximum degree. We show that the minimum broadcast time in any generalized chordal ring is D, D + 1, or D + 2. For the generalized chordal rings of diameter D which have the greatest (or greatest‐known) number of nodes, we then evaluate exactly the minimum broadcast time. It turns out to be D + 1 when D is even and D + 2 when D is odd. For these purposes, we review the construction of these extremal generalized chodal rings. We also review the optimal broadcast schemes for infinite triangular grids, which we use to prove our bounds. Finally, we ask for the maximum number of nodes that can be informed by a broadcast in time t in any generalized chordal ring. We answer this completely for even t and almost completely for odd t. We use a geometric approach, based on plane tessellations. © 2003 Wiley Periodicals, Inc.

List partitions generalize list colorings and list homomorphisms. (We argue that they may be called list "semihomomorphisms.") Each symmetric matrix M over 0,1,* defines a list partition problem. Different choices of the matrix M lead to many well-known graph theoretic problems, often related to graph perfection, including the problem of recognizing split graphs, finding homogeneous sets, clique cutsets, stable cutsets, and so on. The recent proof of the strong perfect graph theorem employs three kinds of decompositions that can be viewed as list partitions. We develop tools which allow us to classify the complexity of many list partition problems and, in particular, yield the complete classification for small matrices M. Along the way, we obtain a variety of specific results, including generalizations of Lovász's communication bound on the number of clique-versus-stable-set separators, polynomial time algorithms to recognize generalized split graphs, a polynomial algorithm for the list version of the clique cutset problem, and the first subexponential algorithm for the skew cutset problem of Chvátal. We also show that the dichotomy (NP-complete versus polynomial time solvable), conjectured for certain graph homomorphism problems, would, if true, imply a slightly weaker dichotomy (NP-complete versus quasi-polynomial) for our list partition problems.

An acyclic homomorphism of a digraph D into a digraph F is a mapping $\phi\colon V(D) \to V(F)$ such that for every arc $uv\in E(D)$, either $\phi(u)=\phi(v)$ or $\phi(u)\phi(v)$ is an arc of F, and for every vertex $v\in V(F)$, the subgraph of D induced on $\phi^{-1}(v)$ is acyclic. For each fixed digraph F we consider the following decision problem: Does a given input digraph D admit an acyclic homomorphism to F? We prove that this problem is NP-complete unless F is acyclic, in which case it is polynomial time solvable. From this we conclude that it is NP-complete to decide if the circular chromatic number of a given digraph is at most q, for any rational number $q > 1$. We discuss the complexity of the problems restricted to planar graphs. We also refine the proof to deduce that certain F-coloring problems are NP-complete.

In this paper we study the problem of recognizing and representing dynamically changing proper interval graphs. The input to the problem consists of a series of modifications to be performed on a graph, where a modification can be a deletion or an addition of a vertex or an edge. The objective is to maintain a representation of the graph as long as it remains a proper interval graph, and to detect when it ceases to be so. The representation should enable one to efficiently construct a realization of the graph by an inclusion-free family of intervals. This problem has important applications in physical mapping of DNA. We give a near-optimal fully dynamic algorithm for this problem. It operates in O(log n) worst-case time per edge insertion or deletion. We prove a close lower bound of $\Omega(\log n/(\log\log n+\log b))$ amortized time per operation in the cell probe model with word-size b. We also construct optimal incremental and decremental algorithms for the problem, which handle each edge operation in O(1) time. As a byproduct of our algorithm, we solve in O(log n) worst-case time the problem of maintaining connectivity in a dynamically changing proper interval graph.

We introduce a parametrized family of graph problems that includes several well-known graph partition problems as special czses.We develop tools which allow us to classify the complexity of many problems in this family, and in particular lead us to a complete classification for small values of the parameters.Along the way, we obtain a variety of specific results including the following: a generalization of a communication bound on the number of clique-versus-independentset separators; polynomial-time algorithms to recognize generalized split graphs; and, a quasi-polynomial algorithm for the Skew Cutset Problem that essentially resolves an open problem posed by Chv&tal.The last two problems have interesting connections to the Strong Perfect Graph Conjecture of Berge.We also observe that the dichotomy (NPcomplete versus polynomial-time solvable) conjectured for certain graph homomorphism problems, would, if true, imply a slightly weaker dichotomy (NP-complete versus quasipolynomial) for our graph partition problems.

There is considerable interest in constructing large networks with given diameter and maximum degree. In certain applications, there is a natural restriction for the networks to be planar. Thus, consider the problem of determining the maximum number of nodes in a planar network with maximum degree Δ and diameter at most k. We have previously proved that this number is at most (roughly) 12kΔ⌊k/2⌋ and there is a trivial lower bound of about (Δ − 1)⌊k/2⌋. We introduce a number of general constructions which substantially improve the lower bound and yield the largest known networks. We also provide a catalog of the best-known networks for small values of Δ and k, many obtained by specialized constructions. © 1998 John Wiley & Sons, Inc. Networks 32:275–281, 1998

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)$.

We discuss the existence of homomorphisms of arbitrary digraphs to a fixed oriented cycle C. Our main result asserts that if the cycle C is unbalanced then a digraph G is homomorphic to. C if and only if (1) every oriented path homomorphic to G is also homomorphic to C, and (2) the length of every cycle of G is a multiple of the length of C. This answers a conjecture from an earlier paper with H. Zhou and generalizes a result proved there. We also show that this characterization does not hold for balanced cycles. We relate these results to work on the complexity of homomorphism problems.

Abstract A graph‐theoretical model is presented for scheduling the transmission of messages in a computer network. A related wiring problem is also discussed; connections with classical edge colorings are exhibited and optimality properties are discussed. © 1993 by John Wiley & Sons, Inc.

Broadcasting is an information dissemination process in which a message is to be sent from a single originator to all members of a network by placing calls over the communication lines of the network. Several previous papers have investigated methods to construct sparse graphs (networks) in which this process can be completed in minimum time from any originator. The graphs produced by these methods contain high degree vertices. [Liestman and Peters, SIAM Journal on Discrete Mathematics, 1 (1988), pp. 531–540 ] and [Bermond and Peyrat, Proceedings of the 19th SE Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, 1988, pp. 283–292] began an investigation of graphs with fixed maximum degree in which broadcasting can be completed in near minimum time. This investigation is continued in this paper by giving lower bounds and constructing bounded degree graphs that allow rapid broadcasting. The constructions use ideas developed by Jerrum and Skyum [IEEE Transactions on Computers, C-33(2), 1984, pp. 190–194], which allow passing from a graph with good average case behaviour to one with good worst case behaviour. In addition, de Bruijn digraphs [de Bruijn, Koninkhjke Nederlandse Akademie Van Wetenschappen, Indagationes Mathematicae, Series A, 49 (1946), pp. 758–764], minimum broadcast graphs, and sparse broadcast graphs [Bermond, Hell, Liestman, and Peters, Discrete Applied Mathematics, to appear] are used. The resulting graphs yield the best broadcasting time known for bounded degree graphs. Also obtained are asymptotic upper and lower bounds for broadcasting time, as the maximum degree increases.

The following problem, known as the H-colouring problem, is studied. An H-colouring of a directed graph D is a mapping $f:V( D ) \to V( H )$ such that $( f( x ),f( y ) )$ is an edge of H whenever $( x,y )$ is an edge of D. The H-colouring problem is the following. Instance: A directed graph D. Question: Does there exist an H-colouring of D? In this paper it is shown that for semicomplete digraphs T the T-colouring problem is NP-complete when T has more than one directed cycle, and polynomially decidable otherwise.

A two-factor of G consists of disjoint cycles that cover $V( G )$. The authors consider the existence problem for two-factors in which the cycles are restricted to having lengths from a prescribed (possibly infinite) set of integers. Theorems are presented which derive the existence of such restricted two-factors in G from their existence in $G - u$ and $G - v $. The possibility of such theorems is then related to the complexity of the corresponding existence problem. In particular, the only four cases in which polynomial algorithms can be expected (in the sense that all other cases are shown to be NP-hard) are identified.

For arbitrary graphs G and H, a G-factor of H is a spanning subgraph of G composed of disjoint copies of G. G-factors are natural generalizations of 1-factors (or perfect matchings), in which G replaces the complete graph on two vertices. Our results show that the perfect matching problem is essentially the only instance of the G-factor problem that is likely to admit a polynomial time bounded solution. Specifically, if G has any component with three or more vertices, then the existence question for G-factors is NP-complete. (In all other cases the question can be resolved in polynomial time.) The notion of a G-factor suggests a natural generalization where G is replaced by an arbitrary family of graphs. This generalization gives rise not only to further NP-completeness results but also to new polynomial algorithms and duality theorems extending results of the traditional theory of matching. An indication of the nature and scope of these new results is presented.

We prove that there exist graphs with n vertices and at most $2n^{5/3} \log n$ edges for which every acyclic orientation has in its transitive closure at least $\begin{pmatrix} n \\ 2 \end{pmatrix} - 10n^{5/3} $ arcs. We conclude that with $2n^{5/3} \log n$ parallel processors n items may be sorted with all comparisons arranged in two time intervals. We also show that $\frac{1}{9}n^{3/2} $ processors are not sufficient to achieve the same end. These results are extended to parallel sorting in k time intervals, and related to other work on parallel sorting. The existence of sorting algorithms achieving the bounds is proved by nonconstructive methods. (The constants quoted in the abstract are somewhat improved in the paper.)

A perfect matching in a graph H may be viewed as a collection of subgraphs of H, each of which is isomorphic to K2, whose vertex sets partition the vertex set of H. This is naturally generalized by replacing K2 by an arbitrary graph G. We show that if G contains a component with at least three vertices then this generalized matching problem is NP-complete. These generalized matchings have numerous applications including the minimization of second-order conflicts in examination scheduling.