Abstract
We give conditions on the minimum numberk of colors, sufficient for the existence of given types of properly edge-colored subgraphs in ak-edge-colored complete graph. The types of subgraphs we study include families of internally pairwise vertex-disjoint paths with common endpoints, hamiltonian paths and hamiltonian cycles, cycles with a given lower bound of their length, spanning trees, stars, and cliques. Throughout the paper, related conjectures are proposed.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bánkfalvi, M., Bánkfalvi, Z.: Alternating hamiltonian circuits in 2-colored complete graphs, Theory of Graphs, Akadémiai Kiadó, Budapest 11–18 (1968)
Benkouar, A., Manoussakis, Y., Paschos, V., Saad, R.: On the complexity of some hamiltonian and eulerian problems in colored complete graphs, LNCS 557 (1991) 190–198 (Springer-Verlag), also to appear in RAIRO on Operations Research (1996)
Bialostocki, A., Dierker, P.: On simple hamiltonian cycles in a 2-colored complete graph. Ars Combinatoria32, 13–16 (1991)
Bollobás, B., Erdös, P.: Alternating hamiltonian cycles. Israel J. Mathematics23, 126–130 (1976)
Chen, C.C., Daykin, D.E.: Graphs with hamiltonian cycles having adjacent lines of different colors. J. Comb. Theory Ser. B21, 135–139 (1976)
Chou, W.S., Manoussakis, Y., Megalakaki, O., Spyratos, M., Tuza, Zs.: Paths through given vertices in edge-colored graphs, Mathématiques. Informatique et Sciences Humaines127(32, 49–58 (1994)
Dirac, G.A.: Some Theorems on abstract graphs. Proc. London Math. Soc.2, 69–81 (1952)
Erdös, P., Gallai, T.: On maximal paths and circuits of graphs. Acta Math. Acad. Sc. Hungar.10, 337–346 (1959)
Erdös, P., Simonovits, M., Sós, V.T.: Anti-Ramsey theorems. Colloq. Math. Soc. J. Bolyai 10 Keszthely (Hungary) 633–643 (1973)
Erdös, P., Stone, A.H.: On the structure of linear graphs. Bull. Amer. Math. Soc.52, 1087–1091 (1946)
Erdös, P., Tuza, Zs.: Rainbow subgraphs in edge-colorings of complete graphs. Annals of Discr. Math.55, 81–88 (1993)
Hell, P., Manoussakis, Y., Tuza, Zs.: Packing problems in edge-colored graphs. Discr. Appl. Math.52, 295–306 (1994)
Manoussakis, Y.: Alternating paths in colored complete graphs. Discr. Appl. Math.72, 247–260 (1994)
Ore, O.: Arc coverings of graphs. Ann. Mat. Pura Appl.55, 315–321 (1961)
Pósa, L.: A theorem concerning Hamilton lines. Magyar Tud. Akad. Mat. Kutato Int. Közl7, 225–226 (1962)
Rödl, V., Tuza, Zs.: Rainbow subgraphs in properly edge-colored graphs. Random Structures and Algorithms3, 175–182 (1992)
Seinsche, D.: On a property of the class ofn-colorable graphs. J. Comb. Theory Ser. B16, 191–193 (1974)
Simonovits, M., Sós, V.T.: On restricted colourings ofK n. Combinatorica4(1, 101–110 (1984)
Author information
Authors and Affiliations
Additional information
Research supported by a European Union PECO grant under identification number CIPA3510PL929589, while on leave at University Paris-XI
Rights and permissions
About this article
Cite this article
Manoussakis, Y., Spyratos, M., Tuza, Z. et al. Minimal colorings for properly colored subgraphs. Graphs and Combinatorics 12, 345–360 (1996). https://doi.org/10.1007/BF01858468
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF01858468