Copyright © 2012 SciRes. OJDM
One can collapse the nodes and of G
wz are connected with an
isomorphic copy ,ij
of , then one can collapse
to a single edge. In this way one recovers the graph
from the graph .
Let us suppose first that the nodes of
have an type coloring . We define
an edge coloring :g G
wz be equal to
v and . If
e adjacent nodes in G, then in the way we have seen
in the proof of Proposition 4 we can extend the coloring
of the edges
wzx y and
h ee graph
Thus the edges of a
tha is a
type coloring as
med in statement (1).
Let us suppose next gE
pe coloring of the edges of
. We define a
:1,2,3fV of tG by setting
he nodes of
be equal toii
wz . We claim that
fv and ijat i
ij imply th
des in In order to proe the claim let
us assume on the contrary that
fv fv, ij
not adjacent noG. v
and the nodes i
v are adjacent in ro
. By Pposi-
gx yg xy
On the other hand the definitiohrines tn of te colohat
,,fvg wzg xy . Similarly, by the
,, ,1iii i1 ,ij
definition of the coloring
we get the contradiction
. Fro this
ld recall t
the proof onoue result
6. The Derived Graph
From we construct a new graph . The
are the edges of , that is, UGE
of are connected
To completee sh
at the problem of deciding if the nodes a given simple
graph have a L type coloring with 3 colors is an NP-
complete problem. Proofs of this well-known result can
be found for example in [6,7].
,GVE be a finite sim
that find a B type coloring of the edges of
G. A possible interpretation of the main result of this
per is that determining the optimal number of colors is
a computationally demanding problem. In practical com-
putations we should be content with suboptimal values of
the number of colors.
we want to
in Γ if and ,,,
yuv are not nodes
of a 4-clique in . In the lack of established terminal-
ogy we call the derived graph of G. The essential con-
nection between G and
is the following result.
Proposition 5. The nodes of have an type col-
oring with k colors if and only if the edges of have a
type coloring with k colors.
The reader will not have any difficulty to check the
veracity of the proposition. The result makes possible to
apply all the greedy coloring techniques developed for
coloring the nodes of a graph. When the graph has n
nodes it may have
edges. For instance when
has 4000 nodes, then may have 10 millions edges. In
this case the adjacency matrix of does not fit into the
memory of an ordinary computer. Thus one should
compute the entries of the adjacency matrix from the
adjacency matrix of during the coloring algorithm.
The most commonly used greedy coloring of the nodes
of a graph takes
On steps. Applying this technique
to the derived graph we get an algorithm whose compu-
tational complexity is
On . The author has carried
out a large scale numerical experiment with this algo-
rithm. The results are encouraging.
 I. M. Bomze, M. Budinich, P. M. Pardalos and M. Pelillo,
“The Maximum Clique Problem,” In: D.-Z. Du and P. M.
Pardalos, Eds., Handbook of Combinatorial Optimization,
Kluwer Academic Pubisher, Dordrecht, 1999, pp. 1-74.
 D. Kumlander, “Some Practical Algorithms to Solve the
Maximal Clique Problem,” Ph.D. Thesis, Tallin Univer-
sity of Technology, Tallinn, 2005.
 R. Carraghan and P. M. Pardalos, “An Exact Algorithm
for the Maximum Clique Problem,” Operation Research
Letters, Vol. 9, No. 6, 1990, pp. 375-382.
 P. R. J. Östergård, “A Fast Algorithm for the Maximum
Clique Problem,” Discrete Applied Mathematics, Vol. 120,
No. 1-3, 2002, pp. 197-207.
 S. Szabó, “Parallel Algorithms for Finding Cliques in a
Graph,” Journal of Physics: Conference Series, Vol. 268,
No. 1, 2011, Article ID: 012030.
 M. R. Garey and S. Johnson, “Computers and Intractabil-
ity: A Guide to the Theory of NP-completeness,” Free-
man, New York, 2003.
 C. H. Papadimitriou, “Computational Complexity,” Ad-
dison-Wesley Publishing Co. Inc., Boston, 1994.