×

zbMATH — the first resource for mathematics

Edge coloring of graphs, uses, limitation, complexity. (English) Zbl 1339.05148
Summary: The known fact that coloring of the nodes of a graph improves the performance of practical clique search algorithm is the main motivation of this paper. We will describe a number of ways in which an edge coloring scheme proposed in [S. Szabó, “Parallel algorithms for finding cliques in a graph”, J. Phys., Conf. Ser. 268, Article ID 012030, 21 p. (2011; doi:10.1088/1742-6596/268/1/012030)] can be used in clique search. The edge coloring provides an upper bound for the clique number. This estimate has a limitation. It will be shown that the gap between the clique number and the upper bound can be arbitrarily large. Finally, it will be shown that to determine the optimal number of colors in an edge coloring is NP-hard.
MSC:
05C15 Coloring of graphs and hypergraphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] I. M. Bomze, M. Budinich, P. M. Pardalos, M. Pelillo, The Maximum Clique Problem, Handbook of Combinatorial Optimization Vol. 4, Kluwer Academic Publisher, 1999. ⇒64 · Zbl 1253.90188
[2] R. Carraghan, P. M. Pardalos, An exact algorithm for the maximum clique problem, Operation Research Letters9 (1990), 375-382. ⇒67 · Zbl 0711.90080
[3] J. Hasselberg, P. M. Pardalos, and G. Vairaktarakis, Test case generators and computational results for the maximum clique problem, Journal of Global Optimization3 (1993), 463-482. ⇒64 · Zbl 0791.90063
[4] D. Kumlander, Some Practical Algorithms to Solve the Maximal Clique problem PhD. Thesis, Tallin University of Technology, 2005. ⇒64 · Zbl 1079.68076
[5] C. Morgan, A Combinatorial Search with Dancing Links, PhD. Thesis, Univ. of Warwick, 1999-2000. ⇒64
[6] J. Mycielski, Sur le coloriage des graphes, Colloq. Math.3 (1955), 161-162. ⇒70 · Zbl 0064.17805
[7] C. H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, Inc., 1994. ⇒64, 74 · Zbl 0833.68049
[8] S. Szabó, Parallel algorithms for finding cliques in a graph, Journal of Physics: Conference Series268 (2011) 012030 ⇒63, 65
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.