zbMATH — the first resource for mathematics

Efficient approximation algorithms for the achromatic number. (English) Zbl 1102.68140
Summary: The achromatic number problem is, given a graph \(G=(V,E)\), to find the greatest number of colors, \(\Psi(G)\), in a coloring of the vertices of \(G\) such that adjacent vertices get distinct colors and for every pair of colors some vertex of the first color and some vertex of the second color are adjacent. This problem is \(NP\)-complete even for trees. We obtain the following new results using combinatorial approaches to the problem:
(1) A polynomial time \(O(|V|^{3/8})\)-approximation algorithm for the problem on graphs with girth at least six. (2) A polynomial time 2-approximation algorithm for the problem on trees. This is an improvement over the best previous 7-approximation algorithm. (3) A linear time asymptotic 1.414-approximation algorithm for the problem when graph \(G\) is a tree with maximum degree \(d(|V|)\), where \(d:N\to N\), such that \(d(|V|)=O(\Psi (G))\). For example, \(d(|V|)=\Theta(1)\) or \(d(|V|)= \Theta(\log|V|)\). (4) A linear time asymptotic 1.118-approximation algorithm for binary trees.
We also improve the lower bound on the achromatic number of binary trees.

68W25 Approximation algorithms
05C85 Graph algorithms (graph-theoretic aspects)
05C15 Coloring of graphs and hypergraphs
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI
[1] Bodlaender, H.L., Achromatic number is NP-complete for cographs and interval graphs, Inform. process. lett., 31, 135-138, (1989) · Zbl 0684.68046
[2] Bollobás, B., The extremal graph theory, (1978), Academic Press London · Zbl 0367.00008
[3] Cairnie, N.; Edwards, K.J., Some results on the achromatic number, J. graph theory, 26, 129-136, (1997) · Zbl 0884.05043
[4] Cairnie, N.; Edwards, K.J., The achromatic number of bounded degree trees, Discrete math., 188, 87-97, (1998) · Zbl 0956.05042
[5] A. Chaudhary, S. Vishwanathan, Approximation algorithms for the achromatic number, in: Proc. Eighth Annu. ACM-SIAM Symp. on Discrete Algorithms (SODA) 1997, pp. 558-563. · Zbl 1321.68494
[6] Cormen, T.H.; Leiserson, C.E.; Rivest, R.L., Introduction to algorithms, (1990), MIT Press Cambridge, MA · Zbl 1158.68538
[7] Edwards, K.J., The harmonious chromatic number of bounded degree trees, Combin. probab. comput., 5, 15-28, (1996) · Zbl 0849.05029
[8] Farber, M.; Hahn, G.; Hell, P.; Miller, D., Concerning the achromatic number of graphs, J. combin. theory, ser. B, 40, 21-39, (1986) · Zbl 0577.05032
[9] R.L. Graham, M. Grötschel, L. Lovász, (Eds.), Handbook of Combinatorics, North-Holland, Amsterdam, 1995.
[10] Harary, F.; Hedetniemi, S., The achromatic number of a graph, J. combin. theory, 8, 154-161, (1970) · Zbl 0195.25702
[11] Harary, F.; Hedetniemi, S.; Prins, G., An interpolation theorem for graphical homomorphisms, Portugaliae math., 26, 453-462, (1967) · Zbl 0187.20903
[12] D.S. Hochbaum (Ed.), Approximation Algorithms for NP-hard Problems, PWS Publishing Company, Boston MA, 1997.
[13] G. Kortsarz, R. Krauthgamer, On approximating the achromatic number, In: Proc. of the 12th Annu. ACM-SIAM Symp. on Discrete Algorithms (SODA), 2001. · Zbl 0977.68063
[14] P. Krysta, K. Loryś, Efficient approximation algorithms for the achromatic number, in: Proc. Seventh Annu. European Symp. on Algorithms (ESA), LNCS, Berlin, Springer, Vol. 1643, 1999, pp. 402-413. · Zbl 0936.05080
[15] G. Kortsarz, S. Shende, Approximating the achromatic number problem on bipartite graphs, in: Proc. 11th Annu. European Symp. on Algorithms (ESA), LNCS, Berlin, Springer, Lecture Notes in Computer Science, Vol. 2832, 2003, pp. 385-396. · Zbl 1266.68230
[16] Motwani, R., The lecture notes on approximation algorithms, department of computer science, (1992), Stanford University Stanford
[17] Saaty, T.L.; Kainen, P.C., The four-color problem: assaults and conquest, (1986), Dover Publishers New York · Zbl 0463.05041
[18] Yannakakis, M.; Gavril, F., Edge dominating sets in graphs, SIAM J. appl. math., 38, 364-372, (1980) · Zbl 0455.05047
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.