Author(s)

Sándor Szabó

Department of Applied Mathematics, Institute of Mathematics and Informatics, University of Pécs, Pécs, Hungary.

Coloring the nodes of a graph is a commonly used technique to speed up clique search algorithms. Coloring the edges of the graph as a preconditioning method can also be used to speed up computations. In this paper we will show that an unconventional coloring scheme of the edges leads to an NP-complete problem when one intends to determine the optimal number of colors.

Maximum Clique; Coloring the Vertices of a Graph; Coloring the Edges of Graph; NP-Complete Problems

S. Szabó, "A Non-Conventional Coloring of the Edges of a Graph," Open Journal of Discrete Mathematics, Vol. 2 No. 4, 2012, pp. 119-124. doi: 10.4236/ojdm.2012.24023.