a ff3 fs6 fc0 sc0 ls0 wsf">coloring with 3 colors. (2) In each such coloring of the
edges of the edges
K B
K
11
,
x
y and
14 14
,
x
y must
receive the same color.
Proof. Let
:1,2,fV3 be an type coloring L
Copyright © 2012 SciRes. OJDM
S. SZABÓ 123
of the nodes of
,
H
VE. By Proposition 1, such col-
oring exists. Using
f
we can construct a type col-
oring of the edges of
B

1,2,3:gF
,
K
WF
. We
can achieve this by setting
,
ii
g
xy to be equal to
i

f
v. If and
i
v
j
v are adjacent nodes in
H
, then
the nodes ,,,
iij j
x
yxy

j
are nodes of a 4-clique in .
K
Now

i
f
vfv and so

j
ii j
,,
g
xy


,
ii
g xy.
The remaining four edges of the 4-clique we color in the
following way. Set
g
xy ,
,
ij
g
xy to be
equal to
i
f
v and set
,
ij
g
yx ,

,
ij
g
yy to
be equal to

j
f
v. A routine inspection shows that the
edges of the 4-clique whose nodes are iij j
, ,,
x
yx
B
:1,2gF
1,
y
K
K
,3
have atype coloring with 3 colors. (The reader will
notice that in fact we used only 2 colors to color the
nodes of the 4-clique.) This coloring procedure can be
repeated for each 4-clique in which has exactly two
primary edges. By Proposition 2, each 4-clique in
has exactly two primary edges and so each edge of
is colored. Therefore the edges of have a type
coloring with 3 colors. This proves statement (1).
B
:1,2
K
K
:fV
In order to prove statement (2) let be
a type coloring of the edges of K. Using g we can
construct an L type coloring

2,3
B
fV

i
,3 of the nodes of H. Simply we set
f
v

i
f
v to be equal to

,
ij
g
xy .
4. The Auxiliary Graph L
Let
,
K
WF

,

be an isomorphic copy of
K
WF
K
such that the sets and W are disjoint.
Using and
W
K


14 14
,xy
K
we construct a new graph by
adding the following edges to .
L

14
yy
L


14 14
,,,yx



14 14
,,xx
14
,
(2)
Figure 9 illustrates the construction. These edges con-
nect the graphs and
K
. The resulting graph is de-
noted by L. The graph L has

22
856 nodes and

4

2 110
L
224
edges. The properties of the
graph we will need later are spelled out in the next
x
14
(x
14
)
y
14
(y
14
)
Figure 9. Connecting the graphs K and K.
proposition.
Proposition 4. (1) The edges of have type col-
oring with 3 colors. (2) In such a coloring of the edges of
the edges
L B
L
11
,x
y
and

14 ,x14
y
cannot receive the
same color.
Proof. By Proposition 3, the edges of
K
have a
type coloring with 3 colors. In such a coloring of the
edges of
B
K
the edges
11
,
x
y and
14 ,14
x
y must
receive the same color. Because the colors of the edges
can be exchanged among each other freely we may in
fact prescribe the colors of these edges. Similarly, the
edges of
K
have a type coloring with 3 colors. In
the coloring of the edges of
B
K
the colors of the edges


11
,xy
and


14 14
,xy
must be equal. Again
the color of these edges can be prescribed. Because of the
presence of the edges (2) the edges
14 14
,
x
y and


14 14
,xy
must receive distinct colors.
5. The Main Result
We are ready to prove the main result of this paper.
Theorem 1. Problem 1 is NP-complete for 3k
.
Proof. Let
,GVE
L
be a finite simple graph. Us-
ing we construct a new graph which
satisfies the following two requirements: 1) If the nodes
of have an type coloring using 3 colors, then the
edges of
G
G
,GVE

G
have a type coloring using 3 colors; 2)
If the edges of
B
G
have a type coloring with 3 col-
ors, then the nodes of G have an type coloring
with 3 colors.
BL
Let be all the vertices of G. This means that
1,,
n
vv
1,,
n
v
i
v
Vv
. We assign two points i and i to
the node for each
w z
,1iin
i
z
. We choose the points
1, 1 to be pair-wise distinct. We con-
nect the nodes i and . In other words
,,n
wwz,,
n
wz
ii
wz, is
an edge of G for each ,1iin
. For each
,,1ijijn
 we consider an isomorphic copy
,,,
,
ijijij
LWF of the auxiliary graph
,LWF. If
i
v and
j
v
G are adjacent nodes in , then we insert
to
G
,i
Lj
such that the edge of

,
ii
wz G
is iden-
tified with the edge
L
,,1 ,,1
,
ij ij
xy of . Further the
,ij
edge
,
j
j
wz of G
is identified with the edge

,,1 ,,1
,
ij ij
xy

of . If and
,ij
Li
v
j
v are not adja-
cent in , then we do not add any new node or new
edge to
G
G
.
We may say that the graph is a blown up version
of the graph . Each node of is replaced by two
connected nodes in
G
G G
G
. Further an isomorphic copy of
the graph plays the role of each edge of in GL G
.
Copyright © 2012 SciRes. OJDM
S. SZABÓ
Copyright © 2012 SciRes. OJDM
124
One can collapse the nodes and of G
i
wi
z
to one
point. If
and
,
ii
wz ,
j
j
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 .
L
G
L,ij
LG
Let us suppose first that the nodes of
,GVE
E
. We
3
,V
have an type coloring . We define
an edge coloring :g G
set

L
,
ii
1: ,2,
2,3 of
fV
1,E
g
wz be equal to
to
i
f
vi
v and . If
j
v
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


,,1 ,,1
,,
i iijij
wzx y and
ar
h ee graph
Thus the edges of a
tha is a
ty


,,1 ,,1
,,
i iijij
wz xy



to eac
have
t
dge
:1
of th
type coloring as

,2,3
,ij
L.
clai
G
B
med in statement (1).
Let us suppose next gE
B
pe coloring of the edges of
,GV
coloring
E

. We define a
:1,2,3fV of tG by setting

i
he nodes of
f
v to


,
be equal toii
g
wz . We claim that

fv and ijat i
v and

fv
ij imply th
j
v are
des in In order to proe the claim let
us assume on the contrary that


i
fv fv, ij
not adjacent noG. v
j
and the nodes i
v,
j
v are adjacent in ro

G
,,
. By Pposi-
tion 4,



,,1 ,,1,,1,,1ijijijij
gx yg xy




g giv
holds.
On the other hand the definitiohrines tn of te colohat



,,fvg wzg xy . Similarly, by the
,, ,1iii i1 ,ij
,,1i
j
,1i


definition of the coloring
m
we get the contradiction



,,



,iii jj
fvg wzgxy


. Fro this

ij
f
vfv
ld recall t
graph a
. This
o th
nd su
proves
the proof onoue result
th
6. The Derived Graph
ple ppose
pa
From we construct a new graph . The
nodes of
G
,UF
are the edges of , that is, UGE
. Two
distinct nodes
,
x
y and
of are connected
,uv
,,uvxy
statement (2).
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].
Let

,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 ,,,
x
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
G
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.
LG
B
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
G
2
On
G
G
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
G
2
On steps. Applying this technique
to the derived graph we get an algorithm whose compu-
tational complexity is
4
On . The author has carried
out a large scale numerical experiment with this algo-
rithm. The results are encouraging.
REFERENCES
[1] 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.
[2] D. Kumlander, “Some Practical Algorithms to Solve the
Maximal Clique Problem,” Ph.D. Thesis, Tallin Univer-
sity of Technology, Tallinn, 2005.
[3] 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.
doi:10.1016/0167-6377(90)90057-C
[4] 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.
doi:10.1016/S0166-218X(01)00290-6
[5] S. Szabó, “Parallel Algorithms for Finding Cliques in a
Graph,” Journal of Physics: Conference Series, Vol. 268,
No. 1, 2011, Article ID: 012030.
doi:10.1088/1742-6596/268/1/012030
[6] M. R. Garey and S. Johnson, “Computers and Intractabil-
ity: A Guide to the Theory of NP-completeness,” Free-
man, New York, 2003.
[7] C. H. Papadimitriou, “Computational Complexity,” Ad-
dison-Wesley Publishing Co. Inc., Boston, 1994.