67
Views
5
CrossRef citations to date
0
Altmetric
Miscellany

The complexity for partitioning graphs by monochromatic trees, cycles and paths

Pages 1357-1362 | Accepted 17 Jun 2004, Published online: 25 Jan 2007

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

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.