A Non-Conventional Coloring of the Edges of a Graph

Sándor Szabó

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

DOI: 10.4236/ojdm.2012.24023                

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.

Keywords

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

Conflicts of Interest

The authors declare no conflicts of interest.

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 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.