Minimal colorings for properly colored subgraphs (Q2563425): Difference between revisions

Sufficient conditions on the minimum number \(k\) of colors guaranteeing the existence of properly edge-colored subgraphs of various types in a \(k\)-edge-colored complete graph are proposed. The types of subgraphs 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; e.g.: the minimum number \(k\) of colors such that every \(k\)-colored complete graph of order \(n\) contains a properly colored Hamiltonian cycle is \({1\over 2}(n-1)(n-2)+2\). Throughout the paper, related conjectures are proposed.