A Non-Conventional Coloring of the Edges of a Graph

DOI: 10.4236/ojdm.2012.24023   PDF   HTML     2,971 Downloads   5,183 Views   Citations


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.

Share and Cite:

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.

Conflicts of Interest

The authors declare no conflicts of interest.


[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 University 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, p. 012030. doi:10.1088/1742-6596/268/1/012030
[6] M. R. Garey and S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-completeness,” Freeman, New York, 2003.
[7] C. H. Papadimitriou, “Computational Complexity,” Addison-Wesley Publishing Co. Inc., Boston, 1994.

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.