Efficient approximation algorithms for the achromatic number

DOI10.1007/3-540-48481-7_35MaRDI QIDQ4938783zbMATH OpenFDO

Authors Piotr Krysta, Krzysztof Loryś

Publication date 27 March 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-48481-7_35

zbMATH Keywords

achromatic numberapproximation algorithmbounded maximum degreegirthNP-complete problemtree

Mathematics Subject Classification ID

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

Review text

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 \textit{M. Farber, G. Hahn, P. Hell} and \textit{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].

Recommendations

• Efficient approximation algorithms for the achromatic number
• Approximation algorithms for the achromatic number.
• On approximating the achromatic number
• On approximating the achromatic number (preliminary version)
• Approximating the achromatic number problem on bipartite graphs
• An approximate algorithm for the chromatic number of graphs
• An approximation algorithm for the achromatic number of mesh-like topologies
• Computationally efficient approximation mechanisms
• Algorithmic bounds for the chromatic number†
• scientific article; zbMATH DE number 3953483

Cited in

(12)

• The achromatic number of bounded degree trees
• Efficient approximation algorithms for the achromatic number
• On approximating the achromatic number
• On approximating the achromatic number (preliminary version)
• Approximation algorithms for the achromatic number.
• scientific article; zbMATH DE number 3882457 (Why is no real title available?)
• An Improved Approximation of the Achromatic Number on Bipartite Graphs
• scientific article; zbMATH DE number 3906522 (Why is no real title available?)
• scientific article; zbMATH DE number 1088659 (Why is no real title available?)
• On the achromatic number of certain distance graphs
• An approximation algorithm for the achromatic number of mesh-like topologies
• Approximating the achromatic number problem on bipartite graphs

This page was built for publication: Efficient approximation algorithms for the achromatic number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4938783)