ABSTRACT 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.
Cite this paper
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.
 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 University 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, p. 012030.
 M. R. Garey and S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-completeness,” Freeman, New York, 2003.
 C. H. Papadimitriou, “Computational Complexity,” Addison-Wesley Publishing Co. Inc., Boston, 1994.