A Non-Conventional Coloring of the Edges of a Graph

Author(s)
Sándor Szabó

Affiliation(s)

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

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

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.

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

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

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.

S. Szabó, "A Non-Conventional Coloring of the Edges of a Graph,"

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.

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