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.