β Scribed by Amitabh Chaudhary; Sundar Vishwanathan
No coin nor oath required. For personal study only.
The achromatic number for a graph G = V E is the largest integer m such that there is a partition of V into disjoint independent sets V 1 V m such that for each pair of distinct sets V i , V j , V i βͺ V j is not an independent set in G. Yannakakis and Gavril (1980, SIAM J. Appl. Math. 38, 364-372) proved that determining this value for general graphs is NP-complete. For n-vertex graphs we present the first o n approximation algorithm for this problem. We also present an O n 5/12 approximation algorithm for graphs with girth at least 5 and a constant approximation algorithm for trees.
π SIMILAR VOLUMES
Let G be a simple graph. The achromatic number Ο(G) is the largest number of colors possible in a proper vertex coloring of G in which each pair of colors is adjacent somewhere in G. For any positive integer m, let q(m) be the largest integer k such that ( k 2 ) β€ m. We show that the problem of dete
The achromatic number of a finite graph G, (G), is the maximum number of independent sets into which the vertex set may be partitioned, so that between any two parts there is at least one edge. For an m-dimensional hypercube P m 2 we prove that there exist constants 0<c 1 <c 2 , independent of m, su
MAX SAT (the maximum s~tisfiability problem) is stated as follows: given a set of clauses with weights, find a truth assignment that maximizes the sum of the weights of the satisfied clauses. In this paper, we consider approxima~ tion algorithms for MAX SAT proposed by Goemans and Williamson and pze