References
References
- Brandstadt , A . (1996) . Partitions of graphs into one or two independent sets and cliques . Discrete Math , 152 : 47 – 54 .
- Enomoto , H . (2001) . Graph partition problems into cycles and paths . Discrete Math , 233 : 93 – 101 .
- Feder , T and Motwani , R . (1995) . Clique partitions, graph compression and speeding-up algorithms . J. Comput. Syst. Sci , 51 : 261 – 272 .
- Garey MR Johnson DS (1979) Computers and Intractability, W.H. Freeman San Francisco
- Holyer , L . (1981) . The NP-completeness of some edge-partition problems . SIAM J. Comput , 10 : 713 – 717 .
- MacGillivray , G and Yu , ML . (1999) . Generalized partitions of graphs . Discrete Appl. Math , 91 : 143 – 153 .
- Feder T Hell P Klein S Motwani R Complexity of graph partition problems Proceedings of Thirty-First Annual ACM Symposium on Theory of Computing, STOC’99 464 472
- Gyárfás , A . (1983) . Vertex coverings by monochromatic paths and cycles . J. Graph Theory , 7 : 131 – 135 .
- Erdös , P , Gyárfás , A and Pyber , L . (1991) . Vertex coverings by monochromatic cycles and trees . J. Comb. Theory Ser. B , 51 : 90 – 95 .
- Haxell , PE and Kohayakawa , Y . (1996) . Partitioning by monochromatic trees . J. Comb. Theory Ser. B , 68 : 218 – 222 .
- Haxell , PE . (1997) . Partitioning complete bipartite graphs by monochromatic cycles . J. Comb. Theory Ser. B , 69 : 210 – 218 .
- Kaneko A Kano M Suzuki K Partitioning complete multipartite graphs by monochromatic trees personal communication
- Broersma , HJ and Li , X . (1997) . Spanning trees with many or few colours in edge-coloured graph . Discuss. Math. Graph Theory , 17 ( 2 ) : 259 – 269 .
- Chang , R and Leu , S . (1997) . The minimum labeling spanning trees . Info. Process. Lett , 63 : 277 – 282 .
- Lawler EL (1976) Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston New York
- Feige , U . (1998) . A threshold of ln n for approximating set cover . J. ACM , 45 : 634 – 652 .
- Hochbaum DS (Ed.) (1997) Approximation Algorithm for NP-Hard Problems, PWS Publishing Company Boston MA