Rankings of Graphs.
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)$.
Introduction
In this paper we consider vertex rankings and edge rankings of graphs. The vertex
ranking problem, also called the ordered coloring problem [15], has received
much attention lately because of the growing number of applications. There
are applications in scheduling problems of assembly steps in manufacturing systems
[19], e.g., edge ranking of trees can be used to model the parallel assembly
of a product from its components in a quite natural manner [6, 12, 13, 14].
Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508
the Netherlands. Email: hansb@cs.ruu.nl. This author was partially supported by the ESPRIT
Basic Research Actions of the EC under contract 7141 (project ALCOM II)
y Department of Computer Science and Engineering, University of Nebraska - Lincoln,
Lincoln, NE 68588-0115, U.S.A. This author was partially supported by the Office of Naval
Research under Grant No. N0014-91-J-1693
z Institut f?r Informatik, TU M-unchen, 80290 M-unchen, Germany. On leave from Univer-
sit-at Trier, Germany
x Department of Mathematics and Computing Science, Eindhoven University of Technology,
P.O.Box 513, 5600 MB Eindhoven, the Netherlands
- IRISA, Campus Universitaire de Beaulieu, 35042 Rennes Cedex, France. On leave
from Friedrich-Schiller-Universit?t, Jena. This author was partially supported by Deutsche
under Kr 1371/1-1
k Fakult?t f?r Mathematik und Informatik, Friedrich-Schiller-Universit?t, Universit?ts-
hochhaus, 07740 Jena, Germany
Computer and Automation Institute, Hungarian Academy of Sciences, H-1111 Budapest,
Kende u. 13-17, Hungary. This author was partially supported by the "OTKA" Research
Fund of the Hungarian Academy of Sciences, Grant No. 2569
Furthermore the problem of finding an optimal vertex ranking is equivalent to
the problem of finding a minimum-height elimination tree of a graph [6, 7].
This measure is of importance for the parallel Cholesky factorization of matrices
[3, 9, 18]. Yet other applications lie in the field of VLSI-layout [17, 26].
The vertex ranking problem 'Given a graph G and a positive integer t,
decide whether - r (G) - t ' is NP-complete even when restricted to cobipartite
graphs since Pothen has shown that the equivalent minimum elimination tree
height problem remains NP-complete on cobipartite graphs [20]. A short proof
of the NP-completeness of vertex ranking is given in Section 3. Much work
has been done in finding optimal rankings of trees. For trees there is a linear-time
algorithm finding an optimal vertex ranking [24]. For the closely related
edge ranking problem on trees a O(n 3 ) algorithm was given in [8]. Recently,
Zhou and Nishizeki obtained an O(n log n) algorithm for optimally edge ranking
trees [28] (see also [29]). Efficient vertex ranking algorithms for permutation,
trapezoid, interval, circular-arc, circular permutation graphs, and cocompara-
bility graphs of bounded dimension are presented in [7]. Moreover, the vertex
ranking problem is trivial on split graphs and it is solvable in linear time on
cographs [25].
In [15], typical graph theoretical questions, as they are known from the
coloring theory of graphs, are investigated. This also leads to a O(
n) bound
for the vertex ranking number of a planar graph and the authors describe a
polynomial-time algorithm which finds a vertex ranking of a planar graph using
only O(
n) colors. For graphs in general there is an approximation algorithm
of performance ratio O(log 2 n) for the vertex ranking number [3, 16]. In [3]
it is also shown that one plus the pathwidth of a graph is a lower bound for
the vertex ranking number of the graph (hence a planar graph has pathwidth
O(
n), which is also shown in [16] using different methods).
Our goal is to extend the known results in both the algorithmic and graph
theoretic directions. The paper is organized as follows. In Section 2 the necessary
notions and preliminary results are given. We study the algorithmic
complexity of determining whether a graph G fulfills - r (G) - t and - 0
respectively, in Sections 3, 4, and 5. In Section 6 we characterize those graphs
for which the vertex ranking number and the chromatic number coincide on
every induced subgraph. Those graphs turn out to be precisely those containing
no path and cycle on four vertices as an induced subgraph; hence, we
obtain a characterization of the trivially perfect graphs [11] in terms of rankings.
Moreover we show that implies that the chromatic number of
G is equal to its largest clique size. In Section 7 we give a recurrence relation
allowing us to compute the edge ranking number of a complete graph.
Preliminaries
We consider only finite, undirected and simple graphs E). Throughout
the paper n denotes the cardinality of the vertex set V and m denotes that of the
edge set E of the graph E). For graph-theoretic concepts, definitions
and properties of graph classes not given here we refer to [4, 5, 11].
E) be a graph. A subset U ' V is independent if each pair
of vertices nonadjacent. A graph E) is bipartite if there is
a partition of V into two independent sets A and B. The complement of the
graph E) is the graph G having vertex set V and edge set ffv; wg j v 6=
Eg. For W ' V we denote by G[W ] the subgraph of E)
induced by the vertices of W , and for X ' E we write G[X] for the graph
and edge set X.
E) be a graph and let t be a positive integer. A
(vertex) t-ranking, called ranking for short if there is no ambiguity, is a coloring
such that for every pair of vertices x and y with
and for every path between x and y there is a vertex z on this path with c(z) ?
c(x). The vertex ranking number of G, - r (G), is the smallest value t for which
the graph G admits a t-ranking.
By definition adjacent vertices have different colors in any t-ranking, thus any t-
ranking is a proper t-coloring. Hence - r (G) is bounded below by the chromatic
number -(G). A vertex - r (G)-ranking of G is said to be an optimal (vertex)
ranking of G.
The edge ranking problem is closely related to the vertex ranking problem.
E) be a graph and let t be a positive integer. An
edge t-ranking is an edge coloring c 0 such that for every pair
of edges e and f with c 0 and for every path between e and f there is
an edge g on this path with c 0 (g) ? c 0 (e). The edge ranking number - 0
r (G) is
the smallest value of t such that G has an edge t-ranking.
Remark 3 There is a one-to-one correspondence between the edge t-rankings
of a graph G and the vertex t-rankings of its line graph L(G). Hence - 0
An edge t-ranking of a graph G is a particular proper edge coloring of G. Hence
r (G) is bounded below by the chromatic index - 0 (G). An edge - 0
r (G)-ranking
of G is said to be an optimal edge ranking of G.
As shown in [7], the vertex ranking number of a connected graph is equal
to its minimum elimination tree height plus one. Thus (vertex) separators and
edge separators are a convenient tool for investigating rankings of graphs. A
subset of a graph E) is said to be a separator if G[V n S] is
disconnected. A subset R ' E of a graph E) is said to be an edge
separator (or edge cut) if G[E n R] is disconnected.
In this paper we use the separator tree for studying vertex rankings. This
concept is closely related to elimination trees (cf.[3, 7, 18]).
Definition 4 Given a vertex t-ranking of a connected
graph E), we assign a rooted tree T (c) to it by an inductive construction,
such that a separator of a certain induced subgraph of G is assigned to each
internal node of T (c) and the vertices of each set assigned to a leaf of T (c) have
different colors:
1. If no color occurs more than once in G, then T (c) consists of a single
vertex r (called root), assigned to the vertex set of G.
2. Otherwise, let i be the largest color assigned to more than one vertex by c.
Then has to be a separator S of G. We create a root r of
T (c) and assign S to r. (The induced subgraph of G corresponding to the
subtree of T rooted at r will be G itself.) Assuming that a separator tree
has already been defined for each connected component
G i of the graph G[V n S], the children of r in T (c) will be the vertices r i
and the subtree of T (c) rooted at r i will be T i (c).
The rooted tree T (c) is said to be a separator tree of G.
Notice that all vertices of G assigned to nodes of T (c) on a path from a leaf to
the root have different colors.
3 Unbounded ranking
It is still unknown whether the edge ranking problem 'Given a graph G and
a positive integer t, decide whether - 0
Remark 3 this problem is equivalent to the vertex ranking problem 'Given
a graph G and a positive integer t, decide whether - r (G) - t ' when restricted
to line graphs.
On the other hand, it is a consequence of the NP-completeness of the minimum
elimination tree height problem shown by Pothen in [20] and the equivalence
of this problem with the vertex ranking problem [6, 7] that the latter
is NP-complete even when restricted to graphs that are the complement of
bipartite graphs, the so-called cobipartite graphs.
For reasons of self-containedness, we start with a short proof of the NP-completeness
of vertex ranking, when restricted to cobipartite graphs. The
following problem, called balanced complete bipartite subgraph (abbre-
viated bcbs) is NP-complete. This is problem [GT24] of [10].
Instance: A bipartite graph E) and a positive integer k.
Question: Are there two disjoint subsets such that
and such that u implies that
Theorem 5 vertex ranking is NP-complete for a cobipartite graphs.
Proof: Clearly the problem is in NP. NP-hardness is shown by reduction from
bcbs.
Let a bipartite graph E) and a positive integer k be given. Let
G be the complement of G, thus G is a cobipartite graph.
We claim that G has a balanced complete bipartite subgraph with 2 \Delta k
vertices if and only if G has a (n \Gamma k)-ranking.
Suppose we have sets W 1
and such that for all u We now construct a k-
ranking of G. Write W
n\Gamma2\Deltak g. We define a vertex ranking c of G as follows:
c(v (1)
One easily observes that c is a vertex (n \Gamma k)-ranking.
Next, let c be a (n\Gammak)-ranking for G. Since G is a cobipartite graph, for each
color, there can be at most two vertices with that color, one lying in V 1 and the
other in V 2 . Therefore, we have k pairs v (1)
with c(v (1)
can assume that W
Now we show that the subgraph induced by the set W 1 [W 2 forms a balanced
complete bipartite subgraph in G. To show this, we prove that each pair of
vertices not adjacent in G. Suppose v (1)
are
adjacent in G. Then, the colors of these vertices must be different. Furthermore,
assume w.l.o.g., that c(v (1)
we have a path (v (1)
c(v (1)
contradicting the fact that c is a ranking. Hence the
subgraph induced by W 1 [W 2 is indeed a balanced complete bipartite subgraph.
This proves the claim, and the NP-completeness of vertex ranking. 2
We show that the analogous result holds for bipartite graphs as well.
Theorem 6 vertex ranking remains NP-complete for bipartite graphs.
Proof: The transformation is from vertex ranking for arbitrary graphs
without isolated vertices. Given the graph G, we construct a graph G
and
Clearly, the constructed graph G 0 is a bipartite graph. Now we show that G
has a t-ranking if and only if G 0 has a (t 1)-ranking.
Suppose G has a t-ranking tg. We construct a coloring -
c for
G 0 in the following way. For the vertices
the vertices
c is a 1)-ranking of
G 0 .
On the other hand, let +1g be a (t +1)-ranking of G 0 . We
show that - c(v) ? 1 for every vertex . Suppose not and let v be a vertex
of V with - wg be an edge incident to v in G. Hence v is
adjacent to (e; 1);
1)-ranking, there are l; l 0 with l 6= l 0 such
that -
implying a path (e;
the assumption that - c is a ranking. This proves that - c(v) ? 1 holds for every
vertex As a consequence, for each edge there is a
vertex
to - c((e; 1)-ranking of G 0 . Now
we define
. The coloring c is a t-ranking of
G since the existence of a path between two vertices v and w of G such that
c(w) and all inner vertices have smaller colors implies the existence of a
path from v to w in G 0 with -
c(w) and all inner vertices having smaller
colors, contradicting the fact that -
c is a 1)-ranking of G 0 . 2
4 Bounded ranking
We show that the 'bounded' ranking problems 'Given a graph G, decide whether
are solvable in linear time for any fixed t. This will be
done by verifying that the corresponding graph classes are closed under certain
operations.
Definition 7 An edge contraction is an operation on a graph G replacing two
adjacent vertices u and v of G by a vertex adjacent to all vertices that were
adjacent to u or v. An edge lift is an operation on a graph G replacing two
adjacent edges fv; wg and fu; wg of G by one edge fu; vg.
Definition 8 A graph H is a minor of the graph G if H can be obtained from
G by a series of the following operations: vertex deletion, edge deletion, and
edge contraction. A graph class G is minor closed if every minor H of every
graph G 2 G also belongs to G.
Lemma 9 The class of graphs satisfying - r (G) - t is minor closed for any
fixed t.
Proof: Since vertex/edge deletion cannot create new paths between
monochromatic pairs of vertices, we only have to show that edge contraction
does not increase the ranking number. Let E) be a graph with
t, and assume is obtained from G by contracting the edge
new vertex c
uv. Suppose c is a t-ranking of G. We construct
of H as follows.
uv
Suppose - c is not a t-ranking of H. Then there is a path
c is a t-ranking of G the vertex c
uv must occur in the path. Depending on its
neighbors in P we can 'decontract' c
uv in the path P into u, v,
getting a path P 0 of G violating the ranking condition, in contradiction to the
choice of c. 2
Corollary 10 For each fixed t, the class of graphs satisfying - r (G) - t can be
recognized in linear time.
Proof: In [1], using results from Robertson and Seymour [22, 23], it is shown
that every minor closed class of graphs that does not contain all planar graphs,
has a linear time recognition algorithm. The result now follows directly from
Lemma 9. 2
As regards edge rankings, a simple argument yields a much stronger assertion
as follows.
Theorem 11 For each fixed t, the class of connected graphs satisfying - 0
t can be recognized in constant time.
Proof: For any fixed t, there are only a finite number of connected graphs G
with
t, as necessary conditions are that the maximum degree of G is
at most t, and the diameter of G is bounded by 2 t \Gamma 1. 2
Certainly, the above theorem immediately implies that the graphs G satisfying
can be recognized in linear time, by inspecting the connected
components separately. This result might have also been obtained via more
involved methods, by using results of Robertson and Seymour on graph immersions
[21]. Similarly, one can show that for fixed t and d, the class of connected
graphs with - r (G) - t and maximum vertex degree d can be recognized in
constant time.
Definition 12 A graph H is an immersion of the graph G if H can be obtained
from G by a series of the following operations: vertex deletion, edge deletion
and edge lift. A graph class G is immersion closed if every immersion H of a
graph G 2 G also belongs to G.
The proof of the following lemma is similar to the one of Lemma 9 and therefore
omitted.
Lemma 13 The class of graphs satisfying - 0
closed for
any fixed t.
Linear-time recognizability of the class of graphs satisfying - 0
now also
follows from Lemma 13, the results of Robertson and Seymour, and the fact
that graphs with - 0
have treewidth at most 2t 2.
5 Computing the vertex ranking number on graphs
with bounded treewidth
In this section, we show that one can compute - r (G) of a graph G with
treewidth at most k in polynomial time, for any fixed k. Such a graph is
also called a partial k-tree. This result implies polynomial time computability
of the vertex ranking number for any class of graphs with a uniform upper
bound on the treewidth, e.g., outerplanar graphs, series-parallel graphs, Halin
graphs.
The notion of treewidth has been introduced by Robertson and Seymour
(see e.g., [22]).
Definition 14 A tree-decomposition of a graph E) is a pair (fX
a collection of subsets of V , and
tree, such that
ffl for all edges fv; wg 2 E there is an i 2 I with v; w
ffl for all is on the path from i to k in T , then
The width of a tree-decomposition (fX
1. The treewidth of a graph E) is the minimum width over all tree-decompositions
of G.
We often abbreviate (fX When the
treewidth of E) is bounded by a constant k, one can find in O(n)
time a tree-decomposition (X; T ) of width at most k, such that I = O(n) and
T is a rooted binary tree [1]. Denote the root of T as r. We say (X; T ) is a
rooted binary tree-decomposition.
Definition 15 A terminal graph is a triple (V; E; Z), with (V; E) an undirected
graph, and Z ' V a subset of the vertices, called the terminals.
To each node i of a rooted binary tree-decomposition (X; T ) of graph
E), we associate the terminal graph G
is a descendant of ig, and g. As
shorthand notation we write p(v; w; G; c; ff), iff there is a path in G from v to
w with all internal vertices having colors, smaller than ff under coloring c. If
G; c; ff), we denote with P (v; w; G; c; ff) the set of paths in G from v to
w with all internal vertices having colors (using color function c), smaller than
ff. In the following, suppose t is given.
be a terminal graph, and let c
be a vertex t-ranking of (V; E). The characteristic of c, Y (c), is
the quadruple (cj Z
ffl cj Z is the function c, restricted to domain Z.
defined true if and only
or there is a vertex x 2 V with G; c; i).
defined
and only if there is a vertex x 2 V with G; c; i) and
G; c; i).
t; 1g is defined by: f 3 (v; w) is the smallest integer
t 0 such that p(v; w; G; c; t 0 ). If there is no path from v to w in G, then
Definition 17 A set of characteristics S of vertex t-rankings of a terminal
graph G is a full set of characteristics of vertex t-rankings for G (in short: a
full set for G), if and only if for every vertex t-ranking c of G, Y (c) 2 S.
set C of vertex t-rankings of a terminal graph G is an example set of
vertex t-rankings for G (in short: an example set for G), if and only if for every
vertex t-ranking c of G, there is an c 0 2 C with Y
the set of characteristics of the elements of C forms a full set of characteristics
of vertex t-rankings for G.
then a full set of characteristics of vertex t-rankings of
(with jZj polynomial in V : there
are O(log k+1 n) possible values for cj Z , 2 O((k+1) log n) possible values for f 1 ,
log n) possible values for f 2 , and there are O(log 1k(k+1) n) possible values
for f 3 . The following lemma, given in [3], shows that we can ensure this
property for graphs with treewidth at most k for fixed k.
Lemma If the treewidth of E) is at most k, then - r
log n).
Let (X; T ) be a rooted binary tree-decomposition of G. Suppose j 2 I is a
descendant of i 2 I in T . Suppose c is a vertex t-ranking of G i . The restriction of
c to G j is the function cj G j
defined by 8v
Clearly, cj G j
is a vertex t-ranking of G j . If c 0 is another vertex t-ranking of G j ,
we define the function R(c; c
Lemma 19 Let (X; T ) be a rooted binary tree-decomposition of E).
Let j be a descendant of i. Let c be a vertex t-ranking of G i , and c 0 be a vertex
t-ranking of G j . If Y (cj G j
vertex t-ranking of G i ,
and Y
Proof: For brevity, we write c
and we write Y (cj G j
We start with proving two claims.
Proof: Let v; w 2 W 1 , and suppose we have a path
We consider those parts of the path p that are part of G
such that each p ff (0 - ff - r) is a path
with all vertices in W 1 , and each p 0
a path in G j .
(Each path is a collection of successive edges, i.e., the last vertex of a path
is the first vertex of the next path.) Write v ff for the first vertex on path
ff and w ff for the last vertex on path p 0
1). Note that
. We now have that there also
exists a path p 00
(In words: there exists a path from v
to w in G j such that all colors of internal vertices are smaller than t 0 , using
coloring c (or, equivalently cj G j
As cj G j
and c 0 have the same characteristics,
there also exists such a path using color function c 0 .) Now, the path formed by
the sequence (p
is a path in G i between v and w
with all colors of internal vertices smaller than t 0 , hence p(v; w; G
shows: p(v; w; G
can be shown in the same way. 2
there exists a vertex
only if there exists a vertex w
(w
claim 20, we have p(v; w; G x be the last vertex on a path
that belongs to W 1 . Write is the last
vertex of p 0 and the first vertex of p 00 . p exists
a path q
Using equality of the characteristics of cj G j
and c 0 , we have that there exists a
vertex
a path from v to w 0 in G i with all internal vertices of color (under color
function c 00 ) smaller that t 0 , hence p(v; w The reverse implication of
the claim can be shown in a similar way. 2
We now show that c 00 is a vertex t-ranking, or, equivalently, that for all
We consider four cases:
1. v; w
c is not a vertex ranking,
contradiction.
2. there exists a
again c is not a
vertex ranking, contradiction.
3. w . Similar to Case 2.
4. v; w all vertices on p belong to W 2 ,
then p is a path in G j , and hence c 0 was not a vertex ranking of G j ,
contradiction. So, there exist vertices on p that belong to W 1 .
Let x be the first vertex on p that belongs to W 1 . Then
must exist vertices
with
a path from v 0 to w 0 with all internal vertices of color (with color function
c) less than t 0 . Hence c is not a vertex ranking, contradiction.
It remains to show that Y
. Suppose
3 ). It follows directly from
Consider v; w
be the vertex with
true. If x
can
and y 2 X j . (Let y be the last vertex in X j on p 1 .) Similarly, we can write
This implies that f 2 (y; z; t 0 ) is true. Hence, there is a vertex x 0 with paths
Also, by Lemma 20, we
have paths p 0
using
path (p 0
12 ) from v to x 0 and path (p 0
22 ) from w to x 0 , it follows that
almost identical argument
shows
.
Finally, it follows directly from Claim 20 that g
We now describe our algorithm. After a rooted binary tree-decomposition
E) has been found (in linear time [1]), the algorithm computes
a full set and an example set for every node i 2 I, in a bottom-up order. Clearly,
when we have a full set for the root node of T , we can determine whether G
has a vertex t-ranking, as we only have to check whether the full set of the root
is non-empty. If so, any element of the example set of the root node gives us a
vertex t-ranking of G.
It remains to show that we can compute for any node i 2 I a full set and
an example set, given a full set and an example set for each of the children
of i 2 I. This is straightforward for the case that i is a leaf node: enumerate
all functions c for each such function c, test whether it is a
vertex t-ranking of G i , and if so, put c in the example set, and Y (c) in the full
set of characteristics.
Next suppose i 2 I has two children j 1 and j 2 . (If i has one child
we can add another child j 2 , which is a leaf in T and has
we have example sets
. We compute a full set S and an
example set Q for G i in the following way:
Initially, we take S and Q to be empty.
For each triple is an element of Q 1 , c 2 is an element of
3 is an arbitrary function c
do the
ffl Check whether for all
(v). If not, skip the
following steps and proceed with the next triple.
ffl Compute the function c : defined as follows:
ffl Check whether c is a vertex t-ranking of G i . If not, skip the following
steps and proceed with the next triple.
ffl If Y (c) 62 S, then put Y (c) in S and put c in Q.
We claim that the resulting sets S and Q form a full set and an example
set for G i . Consider an arbitrary vertex t-ranking c 0 of G i . Let c 1 2 Q 1 be the
vertex t-ranking of Y
that has the same characteristic as c 0
. By definition
of example set, c 1 must exist. Similarly, let c
be defined by c 3
). When the algorithm processes the triple first
test will hold. Suppose c is the function, computed in the second test. Now
note that Hence, by Lemma 19, c is a vertex t-ranking
and has the same characteristic as c 0 . Hence, S will contain Y (c), and Q will
contain a vertex t-ranking of G i with the same characteristic as c and c 0 .
As the size of a full set, and hence of an example set for graphs G i , i 2 I is
polynomial, it follows that the computation of a full set and example set from
these sets associated with the children of the node, can be done in polynomial
time. (There are a polynomial number of triples For each triple, the
computation given above costs polynomial time.) As there are a linear number
of nodes of the tree-decomposition, computing whether there exists a vertex
t-ranking costs polynomial time (assuming testing for each
applicable value of t (see Lemma 18) for the existence of vertex t-rankings of
G, we obtain the following result:
Theorem 22 For any fixed k, there exists a polynomial time algorithm, that
determines the vertex ranking number of graphs G with treewidth at most k,
and finds an optimal vertex ranking of G.
6 The equality -
In this section we consider questions related to the equality of the chromatic
number and the vertex ranking number of graphs.
Theorem 23 If - r holds for a graph G, then G also satisfies
Proof: Suppose that E) has a vertex t-ranking
with -(G). We are going to consider the separator tree T (c) of this t-
ranking. Recall that T (c) is a rooted tree and that every internal node of
T (c) is assigned to a subset of the vertex set of G which is a separator of the
corresponding subgraph of G, namely more than one component arises when
all subsets on the path from the node to the root are deleted from the graph.
Furthermore, all vertices assigned to the nodes of a path from a leaf to the root
of T (c) have pairwise different colors.
The goal of the following recoloring procedure is to show that either
!(G) or we can recolor G to obtain a proper coloring with a smaller number of
colors. However, the latter contradicts the choice of the -(G)-ranking c.
We label the nodes of the tree T (c) according to the following marking rules:
1. Mark a node s of T (c) if the union U(s) of all vertex sets assigned to all
nodes on the path from s to the root is not a clique in G.
2. Also, mark a leaf l of T (c) if the union U(l) of all vertex sets assigned to
all nodes on the path from l to the root is a clique in G, but jU(l)j ! t.
Case 1: There is an unmarked leaf l.
We have and U(l) is a clique. Hence,
Case 2: There is no unmarked leaf.
We will show that this would enable us to recolor G saving one color, contradicting
the choice of c.
Since every leaf of T (c) is marked, every path from a leaf to the root consists
of marked nodes eventually followed by unmarked nodes. Consequently, there
is a collection of marked branches of T (c), i.e., subtrees of T (c) induced by one
node and all its descendants for which all nodes are marked and the father of
the highest node of each branch is unmarked or the highest node is the root of
T (c) itself.
If the root of T (c) is marked then we have exactly one marked branch,
namely T (c) itself. Then, by definition, the separator S assigned to the root is
not a clique. However, none of its colors is used by the ranking for vertices in
Simply, any coloring of the separator S with fewer than j S j colors will
produce a coloring of G with fewer than -(G) colors; contradiction.
If the root is unmarked, then we have to work with a collection of b marked
branches, b ? 1. Notice that all color-1 vertices of G are assigned to leaves of
T (c) and that any leaf of T (c) belongs to some marked branch B. We are going
to recolor the graph G by recoloring the marked branches one by one such that
the new coloring of G does not use color 1. Let us consider a marked branch
B. Let h be its highest node in T (c), and S(h) the set assigned to h. Since h
is marked but the root is unmarked, there must exist a vertex x of S(h) and a
vertex y belonging to U(h) which are nonadjacent. Then c(x) 6= c(y) since all
vertices of U(h) have pairwise different colors.
Assume a leaf of T (c). Hence, x and y,
respectively, is the only color-1 vertex of G assigned to a node of B. We simply
recolor x and y with max(c(x); c(y)).
Finally consider the case c(x) 6= 1 and c(y) 6= 1. All color-1 vertices in the
subgraph of G corresponding to B are recolored with c(x) and x is recolored
with c(y). By the construction of T (c), this does not influence other parts of
the graph, since they are separated by vertex sets with higher colors.
Having done this operation in every marked branch, eventually we get a
new color assignment of G which is still a proper coloring (though usually
not a ranking). Since all leaves of T (c) are marked, and no internal node
of T (c) contains color-1 vertices, color 1 is eliminated from G, contradicting
the assumption - r Consequently, Case 2 cannot occur, implying
This completes the proof. 2
does not imply that G is a perfect graph. (Trivial
counterexamples are of the form is an arbitrary
imperfect graph.) On the other hand, if we require the equality on all induced
subgraphs, then we remain with a relatively small class of graphs that is also
called 'trivially perfect' in the literature (cf. [11]).
Theorem 24 A graph E) satisfies - r
if and only if neither P 4 nor C 4 is an induced subgraph of G.
Proof: The condition is necessary since - r (P 4
2.
Now let G be a P 4 -free and C 4 -free graph. The graphs with no induced
are precisely those in which every connected induced subgraph H
contains a dominating vertex w, i.e., w is adjacent to all vertices of H [27].
Hence, the following efficient algorithm produces an optimal ranking in such
graphs: If then we assign the color !(H) to a
dominating vertex w. Clearly, -(H[V 0
it is easily seen that - r (H[V 0 thus, induction can
be applied. On the other hand, if H is disconnected, then an optimal ranking
can be generated in each of its components separately. 2
7 Edge rankings of complete graphs
While obviously - r (K n not easy to give a closed formula for the edge
ranking number of the complete graph. The most convenient way to determine
r (K n ) seems to introduce a function g(n) by the rules
In terms of this g(n), the following statement can be proved.
Theorem 25 For every positive integer n,
r (K n
Proof: The assertion is obviously true for 3. For larger values of n
we are going to apply induction.
Similarly to vertex t-rankings, the following property holds for every edge
t-ranking of a graph is the largest color occurring more than
once, then the edges with colors form an edge separator of G.
Moreover, doing an appropriate relabeling of these colors
get a new edge t-ranking of G with the property that there is a color j ? i such
that all edges with colors form an edge separator of G which is
minimal under inclusion.
We have to show that the best way to choose this edge separator R with
respect to an edge ranking in a complete graph is by making the two components
of G[E n R] as equal-sized as possible. Let us consider a K n ,
2 be the numbers of vertices in the components, hence and the
corresponding edge separator has size n 1 n 2 . Every edge ranking starting with
this separator has at least
r (K n1
r (K
r (K maxfn1 ;n2 g )
colors, and there is indeed one using exactly that many colors. Defining a 1 :=
repeating the same argument for n 0 so on, we
eventually get a sequence of positive integers a s, such that
a
i!j-s
a j for all s: (1)
Notice that at least the last two terms of any such sequence are equal to 1.
It is easy to see that the number of colors of any edge ranking represented by
a s is equal to
1-i!j-s a i a j , consequently
r (K n
1-i!j-s
a i a
s
a i!
subject to the condition (1). Since a decreasing sort of the sequence maintains
(1) we may assume a 1 - a 2 - a s . Thus, for each value of
1-i!j-s a i a j is attained precisely by the unique sequence satisfying
a
i-j-s a j c for all In particular, we obtain
r (K n
r (K dn=2e
Applying this recursion, it is not difficult to verify that, indeed, - 0
r (K n ) can be
written in the form 1
is the function defined above. 2
Observing that g(2 n we obtain the following interesting
result.
Corollary 26
Conclusions
We studied algorithmic and graph-theoretic properties of rankings of graphs.
For many special classes of graphs, the algorithmic complexity of vertex ranking
is now known. However the algorithmic complexity of vertex ranking
when restricted to chordal graphs or circle graphs is still unknown. Furthermore
it is not even known whether the edge ranking problem is NP-complete.
We started a graph-theoretic study of vertex ranking and edge ranking as
a particular kind of proper (vertex) coloring and proper edge coloring, respec-
tively. Much research has to be done in this direction. It is of particular interest
which of the well-known problems in the theory of vertex colorings and edge
colorings are also worth studying for vertex rankings and edge rankings.



--R

A linear time algorithm for finding tree-decompositions of small treewidth
A tourist guide through treewidth.
Approximating treewidth
Graph Theory with Applications.



Edge ranking of trees.
The multifrontal solution of indefinite sparse symmetric linear equations.
Computers and Intractability: A Guide to the Theory of NP-completeness
Algorithmic Graph Theory and Perfect Graphs.
Optimal node ranking of trees.
Parallel assembly of modular products-an analysis
On an edge ranking problem of trees and graphs.
Ordered colourings.

Area efficient graph layouts for VLSI.
The role of elimination trees in sparse factorization.
Concurrent Design of Products and Processes.
The complexity of optimal elimination trees.
Graph minors.
Graph minors.
Graph minors.

Node ranking and searching on graphs (Abstract).
On a graph partition problem with application to VLSI layout.
The comparability graph of a tree.
Finding optimal edge-rankings of trees
An efficient algorithm for edge-ranking trees
--TR

--CTR
Tak Wah Lam , Fung Ling Yue, Optimal edge ranking of trees in linear time, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.436-445, January 25-27, 1998, San Francisco, California, United States
Kazuhisa Makino , Yushi Uno , Toshihide Ibaraki, Minimum edge ranking spanning trees of split graphs, Discrete Applied Mathematics, v.154 n.16, p.2373-2386, 1 November 2006
Shin-ichi Nakayama , Shigeru Masuyama, A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs, Information Processing Letters, v.103 n.6, p.216-221, September, 2007
Keizo Miyata , Shigeru Masuyama , Shin-ichi Nakayama , Liang Zhao, Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem, Discrete Applied Mathematics, v.154 n.16, p.2402-2410, 1 November 2006
Md. Abul Kashem , M. Ziaur Rahman, An optimal parallel algorithm for c-vertex-ranking of trees, Information Processing Letters, v.92 n.4, p.179-184, November 2004
Dariusz Dereniowski , Adam Nadolski, Vertex rankings of chordal graphs and weighted trees, Information Processing Letters, v.98 n.3, p.96-100, 16 May 2006
Chung-Hsien Hsu , Sheng-Lung Peng , Chong-Hui Shi, Constructing a minimum height elimination tree of a tree in linear time, Information Sciences: an International Journal, v.177 n.12, p.2473-2479, June, 2007
edge ranking;treewidth;vertex ranking;graph algorithms;ranking of graphs;graph coloring