A λ-coloring of a graph G is an assignment of colors from the integer set {0,…,λ} to the vertices of the graph G such that vertices at distance of at most two get different colors and adjacent vertices get colors which are at least two apart. The problem of finding λ-colorings with optimal or near-optimal λ arises in the context of radio frequency assignment. We show that the problem of finding the minimum λ for planar graphs, bipartite graphs, chordal graphs and split graphs is NP-complete. We also give approximation algorithms for λ-coloring and compute upper bounds on the best possible λ for outerplanar graphs, graphs of treewidth k, permutation and split graphs. Except in the case of split graphs, all the above bounds for λ are linear in Δ, the maximum degree of the graph. For split graphs, we give a bound of ½Δ1.5 + 2Δ and we show that there are split graphs G with λ(G) = Ω(Δ1.5). Similar results are also given for variations of the λ-coloring problem.

We consider the degree-preserving spanning tree (DPST) problem: Given a connected graph G, find a spanning tree T of G such that as many vertices of T as possible have the same degree in T as in G. This problem is a graph-theoretical translation of a problem arising in the system-theoretical context of identifiability in networks, a concept which has applications in, for example, water distribution networks and electrical networks. We show that the DPST problem is NP-complete, even when restricted to split graphs or bipartite planar graphs, but that it can be solved in polynomial time for graphs with a bounded asteroidal number and for graphs with a bounded treewidth. For the class of interval graphs, we give a linear time algorithm. For the class of cocomparability graphs, we give an O(n4) algorithm. Furthermore, we present linear time approximation algorithms for planar graphs of a worst-case performance ratio of 1 − ϵ for every ϵ > 0. © 2000 John Wiley & Sons, Inc.

An asteroidal triple (AT) is a set of three vertices such that there is a path between any pair of them avoiding the closed neighborhood of the third. A graph is called AT-free if it does not have an AT. We show that there is an O(n 4 ) time algorithm to compute the maximum weight of an independent set for AT-free graphs. Furthermore, we obtain O(n 4 ) time algorithms to solve the INDEPENDENT DOMINATING SET and the INDEPENDENT PERFECT DOMINATING SET problems on AT-free graphs. We also show how to adapt these algorithms such that they solve the corresponding problem for graphs with bounded asteroidal number in polynomial time. Finally, we observe that the problems CLIQUE and PARTITION INTO CLIQUES remain NP-complete when restricted to AT-free graphs.

An efficient algorithm listing all minimal vertex separators of an undirected graph is given. The algorithm needs polynomial time per separator that is found.

A vertex (edge) coloring $\phi:V\rightarrow \{1,2,\ldots ,t\}$ ($\phi':E\rightarrow \{1,2,\ldots,$ $t\}$) of a graph G=(V,E) is a vertex (edge) t-ranking if, for any two vertices (edges) of the same color, every path between them contains a vertex (edge) of larger color. The {\em vertex ranking number} $\chi_{r}(G)$ ({\em edge ranking number} $\chi_{r}'(G)$) is the smallest value of t such that G has a vertex (edge) t-ranking. In this paper we study the algorithmic complexity of the {\sc Vertex Ranking} and {\sc Edge Ranking} problems. It is shown that $\chi_{r}(G)$ can be computed in polynomial time when restricted to graphs with treewidth at most k for any fixed k. We characterize the graphs where the vertex ranking number $\chi_{r}$ and the chromatic number $\chi$ coincide on all induced subgraphs, show that $\chi_{r}(G)=\chi (G)$ implies $\chi (G)=\omega (G)$ (largest clique size), and give a formula for $\chi_{r}'(K_n)$.

We study a new version of the shortest path problem. Let G = (V, E) be a directed graph. Each are e ∈ E has two numbers attached to it: a transit time b(e, u) and a cost c(e, u), which are functions of the departure time u at the beginning vertex of the arc. Moreover, postponement of departure (i.e., waiting) at a vertex may be allowed. The problem is to find the shortest path, i.e., the path with the least possible cost, subject to the constraint that the total traverse time is at most some number T. Three variants of the problem are examined. In the first one, we assume arbitrary waiting times, where waiting at a vertex without any restriction is allowed. In the second variant, we assume zero waiting times, namely, waiting at any vertex is strictly prohibited. Finally, we consider the general case whre there is a vertex-dependent upper bound on the waiting time at each vertex. Several algorithms with pseudopolynomial time complexity are proposed to optimally solve the problems. First, we assume that all transit times b(e, u) are positive integers. In the last section, we show how to include zero transit times. © 1997 John Wiley & Sons, Inc. Networks 29: 141–149, 1997

In this paper, we show that the treewidth and pathwidth of a permutation graph can be computed in polynomial time. In fact we show that, for permutation graphs, the treewidth and pathwidth are equal. These results make permutation graphs one of the few nontrivial graph classes for which, at the moment, treewidth is known to be computable in polynomial time. Our algorithm, which decides whether the treewidth (pathwidth) is at most some given integer k, can be implemented to run in $O( nk )$ time when the matching diagram is given. We show that this algorithm can easily be adapted to compute the pathwidth of a permutation graph in $O( nk )$ time, where k is the pathwidth.

The authors define a class of languages (called rectilinear) to describe coloured digitized maps and classify them on the basis of their level of succinct representation. The map compression problem is defined as the problem of finding for any given map a shortest description within a given language. For one dimensional maps, that a shortest description can be generated quickly for some languages, but for other languages the problem is NP-hard. A large number of linear time algorithms generate map descriptions whose length is at most twice the minimum.>