List coloring is an NP-complete decision problem even if the total number of colors is three. It is hard even on planar bipartite graphs. We give a polynomial-time algorithm for solving list coloring of permutation graphs with a bounded total number of colors. More generally, we give a polynomial-time algorithm that solves the list-homomorphism problem to any fixed target graph for a large class of input graphs, including all permutation and interval graphs.

A graph is an interval graph if it is the intersection graph of intervals on a line. Interval graphs are known to be the intersection of chordal graphs and asteroidal triple–free graphs, two families where the well-known lexicographic breadth first search (LBFS) plays an important algorithmic and structural role. In this paper we show that interval graphs have a very rich LBFS structure and that by exploiting this structure one can design a linear time, easily implementable, interval graph recognition algorithm.

Asteroidal triple free (AT‐free) graphs have been introduced as a generalization of interval graphs, since interval graphs are exactly the chordal AT‐free graphs. While for interval graphs it is obvious that there is always a linear ordering of the vertices, such that for each triple of independent vertices the middle one intercepts any path between the remaining vertices of the triple, it is not clear that such an ordering exists for AT‐free graphs in general. In this paper we study graphs that are defined by enforcing such an ordering. In particular, we introduce two subfamilies of AT‐free graphs, namely, path orderable graphs and strong asteroid free graphs. Path orderable graphs are defined by a linear ordering of the vertices that is a natural generalization of the ordering that characterizes cocomparability graphs. On the other hand, motivation for the definition of strong asteroid free graphs comes from the fundamental work of Gallai on comparability graphs. We show that cocomparability graphs $\subset$ path orderable graphs $\subset$ strong asteroid free graphs $\subset$ AT‐free graphs. In addition, we settle the recognition question for the two new classes by proving that recognizing path orderable graphs is NP‐complete, whereas the recognition problem for strong asteroid free graphs can be solved in polynomial time.

We examine the bandwidth problem in circular-arc graphs, chordal graphs with a bounded number of leaves in the clique tree, and k-polygon graphs (fixed k). We show that all of these graph classes admit efficient approximation algorithms which are based on exact or approximate bandwidth layouts of related interval graphs. Specifically, we obtain a bandwidth approximation algorithm for circular-arc graphs that executes in O(n log 2 n ) time and has performance ratio 2, which is the best possible performance ratio of any polynomial time bandwidth approximation algorithm for circular-arc graphs. For chordal graphs with at most k leaves in the clique tree, we obtain a performance ratio of 2k in O(k(n+m)) time, and our algorithm for k-polygon graphs has performance ratio 2k 2 and runs in time O(n 3 ).

An independent set of three vertices is called an asteroidal triple if between each pair in the triple there exists a path that avoids the neighborhood of the third. A graph is asteroidal triple-free (AT-free) if it contains no asteroidal triple. The motivation for this investigation is provided, in part, by the fact that AT-free graphs offer a common generalization of interval, permutation, trapezoid, and cocomparability graphs. Previously, the authors have given an existential proof of the fact that every connected AT-free graph contains a dominating pair, that is, a pair of vertices such that every path joining them is a dominating set in the graph. The main contribution of this paper is a constructive proof of the existence of dominating pairs in connected AT-free graphs. The resulting simple algorithm, based on the well-known lexicographic breadth-first search, can be implemented to run in time linear in the size of the input, whereas the best algorithm previously known for this problem has complexity O(|V| 3 ) for input graph G=(V,E). In addition, we indicate how our algorithm can be extended to find, in time linear in the size of the input, all dominating pairs in a connected AT-free graph with diameter greater than 3. A remarkable feature of the extended algorithm is that, even though there may be O(|V| 2 ) dominating pairs, the algorithm can compute and represent them in linear time.

An independent set of three vertices such that each pair is joined by a path that avoids the neighborhood of the third is called an asteroidal triple. A graph is asteroidal triple-free (AT-free) if it contains no asteroidal triples. The motivation for this investigation was provided, in part, by the fact that the AT-free graphs provide a common generalization of interval, permutation, trapezoid, and cocomparability graphs. The main contribution of this work is to investigate and reveal fundamental structural properties of AT-free graphs. Specifically, we show that every connected AT-free graph contains a dominating pair, that is, a pair of vertices such that every path joining them is a dominating set in the graph. We then provide characterizations of AT-free graphs in terms of dominating pairs and minimal triangulations. Subsequently, we state and prove a decomposition theorem for AT-free graphs. An assortment of other properties of AT-free graphs is also provided. These properties generalize known structural properties of interval, permutation, trapezoid, and cocomparability graphs.

The authors determine the algorithmic complexity of domination and variants on cocomparability graphs, a class of perfect graphs containing both the interval and the permutation graphs. Minimum dominating, total dominating, connected dominating, and independent dominating sets can be constructed in polynomial time. On the other hand, DOMINATING CLIQUE and MINIMUM DOMINATING CLIQUE remain NP-complete on cocomparability graphs.

Abstract A graph with n vertices is well covered if every maximal independent set is a maximum independent set and very well covered if every maximal independent set has size n/2. In this work, we study these graphs from an algorithmic complexity point of view. We show that well‐covered graph recognition is co‐NP‐complete and that several other problems are NP‐complete for well‐covered graphs. A number of these problems remain NP‐complete on very well covered graphs, while some admit polynomial time solutions for the smaller class. For both families, the isomorphism problem is as hard as general graph isomorphism.

Cographs are the graphs formed from a single vertex under the closure of the operations of union and complement. Another characterization of cographs is that they are the undirected graphs with no induced paths on four vertices. Cographs arise naturally in such application areas as examination scheduling and automatic clustering of index terms. Furthermore, it is known that cographs have a unique tree representation called a cotree. Using the cotree it is possible to design very fast polynomial time algorithms for problems which are intractable for graphs in general. Such problems include chromatic number, clique determination, clustering, minimum weight domination, isomorphism, minimum fill-in and Hamiltonicity. In this paper we present a linear time algorithm for recognizing cographs and constructing their cotree representation.