A cycle $C$ in a graph is extendable if there exists a cycle $C'$ such that $V(C) \subseteq V(C')$ and $|V(C')|$ = $|V(C)|$ + 1. A graph is cycle extendable if every non-Hamiltonian cycle in the graph is extendable. An open question is whether or not every Hamiltonian chordal graph is cycle extendable. We show that Hamiltonian spider intersection graphs, a subclass of Hamiltonian chordal graphs, are cycle extendable. Our result generalizes known results on cycle extendability in interval graphs and split graphs.

A graph G is the k-leaf power of a tree T if its vertices are leaves of T such that two vertices are adjacent in G if and only if their distance in T is at most k . Then T is a k-leaf root of G . This notion was introduced and studied by Nishimura, Ragde, and Thilikos [2002], motivated by the search for underlying phylogenetic trees. Their results imply an O ( n 3 )-time recognition algorithm for 4-leaf powers. Recently, Rautenbach [2006] as well as Dom et al. [2005] characterized 4-leaf powers without true twins in terms of forbidden subgraphs. We give new characterizations for 4-leaf powers and squares of trees by a complete structural analysis. As a consequence, we obtain a conceptually simple linear-time recognition of 4-leaf powers.

The k-partition problem is as follows: Given a graph G and a positive integer k, partition the vertices of G into at most k parts $A_1, A_2, \ldots , A_k$, where it may be specified that $A_i$ induces a stable set, a clique, or an arbitrary subgraph, and pairs $A_i, A_j (i \neq j)$ be completely nonadjacent, completely adjacent, or arbitrarily adjacent. The list k-partition problem generalizes the k-partition problem by specifying for each vertex x, a list $L(x)$ of parts in which it is allowed to be placed. Many well-known graph problems can be formulated as list k-partition problems: e.g., 3-colorability, clique cutset, stable cutset, homogeneous set, skew partition, and 2-clique cutset. We classify, with the exception of two polynomially equivalent problems, each list 4-partition problem as either solvable in polynomial time or NP-complete. In doing so, we provide polynomial-time algorithms for many problems whose polynomial-time solvability was open, including the list 2-clique cutset problem. This also allows us to classify each list generalized 2-clique cutset problem and list generalized skew partition problem as solvable in polynomial time or NP-complete.

We use a new structural theorem on the presence of two-pairs in weakly chordal graphs to develop improved algorithms. For the recognition problem, we reduce the time complexity from O( mn 2 ) to O( m 2 ) and the space complexity from O( n 3 ) to O( m + n ), and also produce a hole or antihole if the input graph is not weakly chordal. For the optimization problems, the complexity of the clique and coloring problems is reduced from O( mn 2 ) to O( n 3 ) and the complexity of the independent set and clique cover problems is improved from O( n 4 ) to O( mn ). The space complexity of our optimization algorithms is O( m + n ).

A cycle C in a graph is extendable if there exists a cycle ${C^{\prime}}$ such that $V(C) \subseteq V({C^{\prime}})$ and $\mid V({C^{\prime}}) \mid = \mid V(C) \mid + 1$. A graph is cycle extendable if every non‐Hamiltonian cycle in the graph is extendable. An unresolved question is whether or not every Hamiltonian chordal graph is cycle extendable. We show that Hamiltonian graphs in classes such as interval, split, and in some subclasses of strongly chordal graphs, are cycle extendable. We also address efficiently finding a Hamilton cycle in some cases. A unifying theme to our approach is the use of appropriate vertex elimination orders.

The class of weakly triangulated comparability graphs and their complements are generalizations of interval graphs and chordal comparability graphs. We show that problems on these classes of graphs can be solved efficiently by transforming them into problems on chordal bipartite graphs. We show that recognition and independent set on weakly triangulated comparability graphs can be solved in O(n 2 ) time in this manner, and that the number of weakly triangulated comparability graphs is $2^{\Theta ( n {{\log}^2} n)}$.\ We also give algorithms to compute transitive closure and transitive reduction in O(n 2 loglogn) time if the underlying undirected graph of the transitive closure is a weakly triangulated comparability graph.

An undirected graph G is a circular permutation graph if it can be represented by the following intersection model: Each vertex of G corresponds to a chord in the annular region between two concentric circles, and two vertices are adjacent in G if and only if their corresponding chords intersect each other exactly once. Circular permutation graphs are a generalization of permutation graphs. Rotem and Urrutia introduced and characterized this class of graphs and their characterization yields an O(n2.376) algorithm for recognizing circular permutation graphs. Gardner gave an O(n2) recognition algorithm. We provide an alternate characterization and show that an O(m + n) recognition algorithm can be derived from the new characterization. Our algorithm also constructs the intersection model when the input graph is a circular permutation graph (CPG). © 1996 John Wiley & Sons, Inc.