Efficient approximation algorithms for the achromatic number. (English) Zbl 0936.05080

Krysta, Piotr; Loryś, Krzysztof

Nešetřil, Jaroslav (ed.), Algorithms - ESA ’99. 7th annual European symposium, Prague, Czech Republic, July 16-18, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1643, 402-413k (1999).

The achromatic number of a graph is the maximum size \(k\) of a vertex coloring of the graph, where every pair of the \(k\) colors is assigned to some two adjacent vertices and adjacent vertices are colored with different colors. It is well known that the achromatic number problem is NP-complete even for bipartite graphs or for trees. An \(\alpha \)-approximation algorithm for a maximization problem \(P\) is a polynomial time algorithm, that always computes a solution to the problem \(P\), whose value is at least a factor \(\frac{1}{\alpha }\) of the optimum.
In this paper improved polynomial time approximation algorithms for the achromatic number problem on graphs with large girth and for trees, and linear time approximation algorithms for trees with bounded maximum degree are presented (e.g., a 2-approximation algorithm for trees, an \(O(n^{3/8})\)-approximation algorithm for graphs with girth at least six or an asymptotic 1.155-approximation linear time algorithm for binary trees). Also the lower bound of M. Farber, G. Hahn, P. Hell and D. Miller [J. Comb. Theory, Ser. B 40, 21-39 (1986 Zbl 0558.05024)] for the achromatic number of trees with maximum degree bounded by three is improved.
For the entire collection see [Zbl 0918.00032].

Reviewer: I.Tomescu (Bucureşti)

MSC:

05C85	Graph algorithms (graph-theoretic aspects)
05C15	Coloring of graphs and hypergraphs

Keywords:

achromatic number; NP-complete problem; tree; approximation algorithm; girth; bounded maximum degree