{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T21:55:06Z","timestamp":1767995706051,"version":"3.49.0"},"reference-count":80,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,9,1]],"date-time":"2008-09-01T00:00:00Z","timestamp":1220227200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2008,9]]},"DOI":"10.1007\/s00373-008-0789-5","type":"journal-article","created":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T19:24:56Z","timestamp":1221247496000},"page":"237-263","source":"Crossref","is-referenced-by-count":86,"title":["Monochromatic and Heterochromatic Subgraphs in Edge-Colored Graphs - A Survey"],"prefix":"10.1007","volume":"24","author":[{"given":"Mikio","family":"Kano","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xueliang","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,9,13]]},"reference":[{"key":"789_CR1","doi-asserted-by":"crossref","unstructured":"Akbari, S., Alipour, A.: Multicolored trees in complete graphs. J. Graph Theory 54, 221\u2013232 (2006)","DOI":"10.1002\/jgt.20204"},{"key":"789_CR2","unstructured":"Aldred, R.E.L., Wormald, N.C.: More on the linear k\u2013arboricity of regular graphs. Australas. J. Combin. 18, 97\u2013104 (1998)"},{"key":"789_CR3","unstructured":"Akiyama, J., Exoo, G., Harary, F.: Covering and packing in graphs III, Cyclic and acyclic invariants. Math. Slovaca 30, 405\u2013417 (1980)"},{"key":"789_CR4","doi-asserted-by":"crossref","unstructured":"Albert, M., Frieze, A., Reed, B.: Multicoloured Hamilton cycles, Electronic J. Combin. 2, \u266f R10 (1995)","DOI":"10.37236\/1204"},{"key":"789_CR5","doi-asserted-by":"crossref","unstructured":"Alexeev, B.: On lengths of rainbow cycles. Electron. J. Combin. 13, \u266fR105 (2006)","DOI":"10.37236\/1131"},{"key":"789_CR6","unstructured":"Alon, N., Brualdi, R.A., Shader, B.L.: Multicolored forests in bipartite decompositions of graphs. J. Combin. Theory, Ser. B 53, 143\u2013148 (1991)"},{"key":"789_CR7","doi-asserted-by":"crossref","unstructured":"Alon, N., Gutin, G.: Properly colored Hamiltonian cycles in edge-colored complete graphs. Random Structures Algorithms 11, 179\u2013186 (1997)","DOI":"10.1002\/(SICI)1098-2418(199709)11:2<179::AID-RSA5>3.0.CO;2-P"},{"key":"789_CR8","doi-asserted-by":"crossref","unstructured":"Alon, N., Jiang, T., Miller, Z., Pritikin, D.: Properly colored subgraphs and rainbow subgraphs in edge colorings with local constraints. Random Structures Algorithms 23 (4), 409\u2013433 (2003)","DOI":"10.1002\/rsa.10102"},{"key":"789_CR9","doi-asserted-by":"crossref","unstructured":"Axenovich, M., Jiang, T., Tuza, Zs.: Local anti-Ramsey numbers of graphs. Combin. Probab. Comput. 12 (5\u20136), 495\u2013511 (2003)","DOI":"10.1017\/S0963548303005868"},{"key":"789_CR10","unstructured":"Ayel, J.: \u201cSur l\u2019existence de deux cycles suppl\u00e9muntaires unicolor\u00e9s disjoints et de couleurs diff\u00e9rentes dans un graphe complet bicolore,\u201d Thesis, University of Grenoble, 1979"},{"key":"789_CR11","doi-asserted-by":"crossref","unstructured":"Bermond, J.C., Fouquent, J.L., Habibi, M., P\u0301eroche, B.: On linear k-arboricity. Discrte Math. 52, 123\u2013132 (1984)","DOI":"10.1016\/0012-365X(84)90075-X"},{"key":"789_CR12","unstructured":"Bialostocki, A., Voxman, W.: On monochromatic-rainbow generalizations of two Ramsey type theorems. Ars Combin. 68, 131\u2013142 (2003)"},{"key":"789_CR13","unstructured":"Bierbrauer, J., Dierker, P.: Monochromatic connected subgraphs in a multicoloring of the complete graph, Preprint"},{"key":"789_CR14","unstructured":"Bollob\u00e1s, B., Erd\u0151s, P.: Alternating Hamiltonian cycles. Isr. J. Math. 23, 126\u2013131 (1976)"},{"key":"789_CR15","doi-asserted-by":"crossref","unstructured":"Broersma, H.J., Li, X.: Spanning trees with many or few colors in edge-colored graphs. Discuss. Math. Graph Theory 17, 259\u2013269 (1997)","DOI":"10.7151\/dmgt.1053"},{"key":"789_CR16","unstructured":"Broersma, H.J., Li, X., Woeginger, G., Zhang, S.: Paths and cycles in colored graphs. Australasian J. Combin. 31, 297\u2013309 (2005)"},{"key":"789_CR17","unstructured":"Brualdi, R.A., Hollingsworth, S.: Multicolored trees in complete graphs. J. Combin. Theory, Ser. B 68, 310\u2013313 (1996)"},{"key":"789_CR18","doi-asserted-by":"crossref","unstructured":"Brualdi, R.A., Hollingsworth, S.: Multicolored forests in complete bipartite graphs. Disrete Math. 240, 239\u2013245 (2001)","DOI":"10.1016\/S0012-365X(00)00159-X"},{"key":"789_CR19","doi-asserted-by":"crossref","unstructured":"Chang, R.S., Leu, S.J.: The minimum labelling spanning trees. Inform. Process. Lett. 63, 277\u2013282 (1997)","DOI":"10.1016\/S0020-0190(97)00127-0"},{"key":"789_CR20","unstructured":"Chartrand, G., Lesniak, L.: Graphs and Combinatorics (third edition). Chapman & Hall, New York (1996)"},{"key":"789_CR21","doi-asserted-by":"crossref","unstructured":"Chen, H., Jin, Z.M., Li, X., Tu, J.H.: Heterochromatic tree partition numbers for complete bipartite graphs. Discrete Math., in press, doi:10.1016\/j.disc.2007.07.085","DOI":"10.1016\/j.disc.2007.07.085"},{"key":"789_CR22","doi-asserted-by":"crossref","unstructured":"Chen, H., Li, X.: Long heterochromatic paths in edge-colored graphs. Electron. J. Combin. 12, $$\\sharp$$ R33 (2005)","DOI":"10.37236\/1930"},{"key":"789_CR23","doi-asserted-by":"crossref","unstructured":"Chen, H., Li, X.: Color degree and color neighborhood union conditions for long heterochromatic paths in edge-colored graphs. arXiv:math.CO\/0512144 v1 7 Dec 2005","DOI":"10.37236\/1930"},{"key":"789_CR24","doi-asserted-by":"crossref","unstructured":"Chen, H., Li, X.: Color neighborhood union conditions for long heterochromatic paths in edge-colored graphs. Electron. J. Combin. 14, $$\\sharp$$ R77 (2007)","DOI":"10.37236\/995"},{"key":"789_CR25","unstructured":"Chou, W.S., Manoussakis, Y., Megalalaki, O., Spyratos, M., Tuza, Zs.: Paths through fixed vertices in edge-colored graphs. Math. Inf. Sci. Hun. 32, 49\u201358 (1994)"},{"key":"789_CR26","doi-asserted-by":"crossref","unstructured":"Constantine, G.M.: Colorful isomorphic spanning trees in complete graphs. Ann. Combin. 9, 163\u2013167 (2005)","DOI":"10.1007\/s00026-005-0247-5"},{"key":"789_CR27","doi-asserted-by":"crossref","unstructured":"Cooper, C., Frieze, A.: Multicoloured Hamilton cycles in random graphs; an anti-Ramsey threshold. Electron. J. Combin. 2, $$\\sharp$$ R19 (1995)","DOI":"10.37236\/1213"},{"key":"789_CR28","doi-asserted-by":"crossref","unstructured":"D\u00e9nes, J., Keedwell, A.D.: Latin Squres: New Developments in the Theory and Applications. Ann. Discrete Math. 46, North-Holland, New York, 1991","DOI":"10.1016\/S0167-5060(08)70969-5"},{"key":"789_CR29","unstructured":"El-Zanati, S.I., Plantholt, M.J., Sissokho, P.A., Spence, L.E.: On the existence of rainbow 1-factor in 1-factorizaions of $$K_{rn}^{(r)}$$ . J. Combin. Des., preprint"},{"key":"789_CR30","doi-asserted-by":"crossref","unstructured":"Erd\u0151s, P., Galvin, F.: Monochromatic infinite paths. Discrete Math. 113, 59\u201370 (1993)","DOI":"10.1016\/0012-365X(93)90508-Q"},{"key":"789_CR31","unstructured":"Erd\u0151s, P., Gallai, T.: On maximal paths and circuits of graphs. Acta. Math. Acad. Sc. Hungar. 10, 337\u2013356 (1959)"},{"key":"789_CR32","unstructured":"Erd\u0151s, P., Gy\u00e1rf\u00e1s, A., Pyber, L.: Vertex coverings by monochromatic cycles and trees. J. Combin. Theory Ser. B 51, 90\u201395 (1991)"},{"key":"789_CR33","unstructured":"Erd\u0151s, P., Nesetril, J., R\u0151dl, V.: Some problems related to partitions of edges of a graph. Graphs and Other Combinatorial Topics, Teubner, Leipzig, 54\u201363 (1983)"},{"key":"789_CR34","unstructured":"Erd\u0151s, P., Tuza, Zs.: Rainbow Hamiltonian paths and canonically colored subgraphs in infinite complete graphs. Math. Pannon 1 (1), 5\u201313 (1990)"},{"key":"789_CR35","doi-asserted-by":"crossref","unstructured":"Frieze, A., Reed, B.: Polychromatic Hamilton cycles. Discrete Math. 118, 69\u201374 (1993)","DOI":"10.1016\/0012-365X(93)90054-W"},{"key":"789_CR36","doi-asserted-by":"crossref","unstructured":"F\u00fcredi, Z.: Maximum degree and fractional matchings in uniform hypergraphs. Combinatorica 1, 155\u2013162 (1981)","DOI":"10.1007\/BF02579271"},{"key":"789_CR37","doi-asserted-by":"crossref","unstructured":"F\u00fcredi, Z.: Matchings and covers in hypergraphs. Graphs Combin. 4, 115\u2013206 (1988)","DOI":"10.1007\/BF01864160"},{"key":"789_CR38","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W.H. Freeman, San Francisco, 1979"},{"key":"789_CR39","unstructured":"Gerencs\u00e9r, L., Gy\u00e1rf\u00e1s, A.: On Ramsey-type problems, Ann. Univ. Sci. Bud. de Rol. E\u00f6tv\u00f6s Sect. Math. 10, 167\u2013170 (1967)"},{"key":"789_CR40","unstructured":"Gy\u00e1rf\u00e1s, A.: Partition coverings and blocking sets in hypergraphs (in Hungarian). Tanulm\u00e1nyok-MTA Sz\u00e1mit\u00e1stechn. Automat. Kutat\u00f3 Int. Budapest 71, 62\u00a0pp. (1977)"},{"key":"789_CR41","doi-asserted-by":"crossref","unstructured":"Gy\u00e1rf\u00e1s, A.: Vertex coverings by monochromatic paths and cycles. J. Graph Theory 7, 131\u2013135 (1983)","DOI":"10.1002\/jgt.3190070116"},{"key":"789_CR42","unstructured":"Gy\u00e1rf\u00e1s, A.: Covering complete graphs by monochromatic paths, in Irregularities of Partitions, Algorithms and Combinatorics, Springer-Verlag 8, 89\u201391 (1989)"},{"key":"789_CR43","unstructured":"Gy\u00e1rf\u00e1s, A., Jagota, A., Schelp, R.H.: Monochromatic path covers in nearly complete graphs. J. Combin. Math. Combin. Comput. 25, 129\u2013144 (1997)"},{"key":"789_CR44","unstructured":"Gy\u00e1rf\u00e1s, A., Ruszink\u00f3, M., S\u00e1rk\u00f6zy, G.N., Szemer\u00e9di, E.: An improved bound for the monochromatic cycle partition number. J. Combin. Theory Ser. B 96, 855\u2013873 (2006)"},{"key":"789_CR45","doi-asserted-by":"crossref","unstructured":"Gy\u00e1rf\u00e1s, A., Simonyi, G.: Edge colorings of complete graphs without tricolored triangles. J. Graph Theory 46, 211\u2013216 (2004)","DOI":"10.1002\/jgt.20001"},{"key":"789_CR46","doi-asserted-by":"crossref","unstructured":"Hahn, G., Thomassen, C.: Path and cycle sub-Ramsey numbers and an edge coloring conjecture. Discrete Math. 62, 29\u201333 (1986)","DOI":"10.1016\/0012-365X(86)90038-5"},{"key":"789_CR47","unstructured":"Hajnal, A., Komj\u00e1th, P., Soukup, L., Szalkai, I.: Decompositions of edge-colored infinite complete graphs. Colloq. Math. Soc. J\u00e1nos Bolyai 52, 277\u2013280 (1987)"},{"key":"789_CR48","unstructured":"Haxell, P.E., Kohayakawa, Y.: Partitioning by monochromatic trees. J. Combin. Theory, Ser. B 68, 218\u2013222 (1996)"},{"key":"789_CR49","unstructured":"Haxell, P.E.: Partititoning complete bipartite graphs by monochromatic cycles. J. Combin. Theory, Ser. B 69, 210\u2013218 (1997)"},{"key":"789_CR50","doi-asserted-by":"crossref","unstructured":"Hu, L., Li, X.: Sufficient conditions for the existence of perfect heterochromatic matchings in colored graphs. Discrete Geometry, Combinatorics and Graph Theory, 7th China-Japan Conference, CJCDGCGT 2005, Lecture Notes in Computer Science, Vol. 4381, 2007","DOI":"10.1007\/978-3-540-70666-3_6"},{"key":"789_CR51","doi-asserted-by":"crossref","unstructured":"Jiang, T., West, D.B.: Edge colorings of complete graphs that avoid polychromatic trees. Discrete Math. 274, 137\u2013145 (2005)","DOI":"10.1016\/j.disc.2003.09.002"},{"key":"789_CR52","unstructured":"Jin, Z.M., Kano, M., Li, X., Wei, B.: Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees. J. Comb. Optim. 11, 445\u2013454 (2006)"},{"key":"789_CR53","unstructured":"Jin, Z.M., Li, X.: The complexity for partitioning graphs by monochromatic trees, cycles and paths. Int. J. Comput. Math. 81, 1357\u20131362 (2004)"},{"key":"789_CR54","unstructured":"Jin, Z.M., Li, X.: Vertex partitions of r-edge-colored graphs. Appl. Math. J. Chinese Univ. Ser. B. 23(1), 120\u2013126 (2008)"},{"key":"789_CR55","unstructured":"Jin, Z.M., Li, X.: Spanning trees with many colors in edge-colored graphs. J. Xinjiang University 23(Supp.), 12\u201314 (2006)"},{"key":"789_CR56","unstructured":"Jin, Z.M., Li, X.: Partitioning complete graphs by rainbow trees, arXiv:0711.2849 [math.CO] 19 Nov 2007"},{"key":"789_CR57","unstructured":"Kaneko, A., Kano, M., Suzuki, K.: Three edge disjoint multicolored spanning trees in complete graphs, Preprint 2003"},{"key":"789_CR58","doi-asserted-by":"crossref","unstructured":"Kaneko, A., Kano, M., Suzuki, K.: Partitioning complete multipartite graphs by monochromatic trees. J. Graph Theory 48, 133\u2013141 (2005)","DOI":"10.1002\/jgt.20044"},{"key":"789_CR59","unstructured":"Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Holt, Tinehart and Winston, New York, 1976"},{"key":"789_CR60","doi-asserted-by":"crossref","unstructured":"Li, H.: A generalization of Gallai-Roy theorem. Graphs Combin. 17, 681\u2013685 (2001)","DOI":"10.1007\/PL00007256"},{"key":"789_CR61","unstructured":"Li, H., Li, X., Liu, G., Wang, G.: The heterochromatic matchings in edge-colored bipartite graphs. Ars Combin., in press"},{"key":"789_CR62","unstructured":"Li, H., Wang, G.: Color degree and heterochromatic matchings in edge-colored bipartite graphs. Utilitas Math., to appear"},{"key":"789_CR63","unstructured":"Li, X., Xu, Z.X.: On the existence of a rainbow 1-factor in proper coloring of K rn (r) . arXiv:0711.2847 [math.CO] 19 Nov 2007"},{"key":"789_CR64","doi-asserted-by":"crossref","unstructured":"Li, X., Zhang, X.Y.: On the minimum monochromatic or multicolored subgraph partition problems. Theoretical Computer Science 385, 1\u201310 (2007)","DOI":"10.1016\/j.tcs.2007.04.033"},{"key":"789_CR65","unstructured":"Li, X., Zheng, J.: Monochromatic and heterochromatic subgraphs problems in a randomly colored graph, Preprint 2005 (arXiv:0711.3827 [math.CO] 24 Nov 2007)"},{"key":"789_CR66","unstructured":"\u0141uczak, T., R\u00f6dl, V., Szemer\u00e9di, E.: Partitioning two-coloured complete graphs into two monochromatic cycles. Probab. Combin. Comput. 7, 423\u2013436 (1998)"},{"key":"789_CR67","doi-asserted-by":"crossref","unstructured":"Manoussakis, Y., Spyratos, M., Tuza, Zs.: Cycles of given color paterns. J. Graph Theory 21 (2), 153\u2013162 (1996)","DOI":"10.1002\/(SICI)1097-0118(199602)21:2<153::AID-JGT4>3.0.CO;2-Q"},{"key":"789_CR68","doi-asserted-by":"crossref","unstructured":"Montellano-Ballesteros, J.J.: An anti-Ramsey theorem on edge-cuts. Discuss. Math. Graph Theory 26, 19\u201321 (2006)","DOI":"10.7151\/dmgt.1297"},{"key":"789_CR69","unstructured":"Pyber, L., R\u00f6dl, V., Szemer\u00e9di, E.: Dense graphs without 3-regular subgraphs. J. Combin. Theory, Ser. B 63, 41\u201354 (1995)"},{"key":"789_CR70","unstructured":"Rado, R.: Monochromatic paths in graphs. Ann. Discrete Math. 3, 197\u2013194 (1978)"},{"key":"789_CR71","doi-asserted-by":"crossref","unstructured":"R\u00f6dl, V., Tuza, Zs.: Rainbow subgraphs in properly edge-colored graphs. Random Structures Algorithms 3, 175\u2013182 (1992)","DOI":"10.1002\/rsa.3240030207"},{"key":"789_CR72","unstructured":"Ryser, H.J.: Neuere probleme der kombinatorik, In: \"Vortrage uber Kombinatorik Oberwolfach\", Mathematiches Forschungsinstitut Oberwolfach, pp 24\u201329, Juli 1967"},{"key":"789_CR73","unstructured":"S\u00e1rk\u00f6zy, G.N., Selkow, S.M.: Vertex partitions by connected monochromatic k-regular graphs. J. Combin. Theory, Ser. B 78, 115\u2013122 (2000)"},{"key":"789_CR74","unstructured":"Stein, S.K.: Transversals of Latin squares and their generalizations. Pacific J. Math. 59(2), 567\u2013575 (1975)"},{"key":"789_CR75","doi-asserted-by":"crossref","unstructured":"Suzuki, K.: A necessary and sufficient contidion for the existence of a heterochromatic spanning tree in a graph. Graphs Combin. 22, 261\u2013269 (2006)","DOI":"10.1007\/s00373-006-0662-3"},{"key":"789_CR76","unstructured":"Thomassen, C.: Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5. J. Combin. Theory, Ser. B 75, 100\u2013109 (1999)"},{"key":"789_CR77","unstructured":"Tuza, Zs.: Some special cases of Rysers Conjecture, Preprint (1978)"},{"key":"789_CR78","unstructured":"Hans-Christoph W., Multicriteria approximation of network design and network upgrade problems, Chapter 2, Ph.D. Dissertation, Bayerischen Julius-Maximilians Universit\u00e4t, W\u00fczburg, March 2001"},{"key":"789_CR79","unstructured":"Woolbright, D.E., Fu, H.L.: On the existence of rainbows in 1-factorizations of K 2n . J. Combin. Des. 6, 1\u201320 (1998)"},{"key":"789_CR80","doi-asserted-by":"crossref","unstructured":"Yuster, R.: Rainbow H-factors. Electron. J. Combin. 13, $$\\sharp R$$ 13 (2006)","DOI":"10.37236\/1039"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-008-0789-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00373-008-0789-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-008-0789-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,19]],"date-time":"2023-05-19T23:08:54Z","timestamp":1684537734000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00373-008-0789-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,9]]},"references-count":80,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,9]]}},"alternative-id":["789"],"URL":"https:\/\/doi.org\/10.1007\/s00373-008-0789-5","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,9]]}}}