Minimal colorings for properly colored subgraphs
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.
- Minimal coloring and strength of graphs
- Minimum coloring problems with weakly perfect graphs
- Subcolorings and the subchromatic number of a graph
- Minimum order of graphs with given coloring parameters
- Total colorings of graphs with minimum sum of colors
- Coloring subgraphs with restricted amounts of hues
- On some properties of suboptimal colorings of graphs
- scientific article; zbMATH DE number 861338
- scientific article; zbMATH DE number 140082
- Minimum total coloring of planar graph
- Alternating Hamiltonian cycles
- Arc coverings of graphs
- Graphs with Hamiltonian cycles having adjacent lines different colours
- Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results
- scientific article; zbMATH DE number 434896 (Why is no real title available?)
- scientific article; zbMATH DE number 54775 (Why is no real title available?)
- scientific article; zbMATH DE number 762736 (Why is no real title available?)
- scientific article; zbMATH DE number 3186565 (Why is no real title available?)
- On a property of the class of n-colorable graphs
- On maximal paths and circuits of graphs
- On restricted colourings of \(K_ n\)
- On the structure of linear graphs
- Packing problems in edge-colored graphs
- Rainbow subgraphs in properly edge‐colored graphs
- Some Theorems on Abstract Graphs
- Properly edge-colored theta graphs in edge-colored complete graphs
- Properly colored \(C_4\)'s in edge-colored graphs
- On the maximal colorings of complete graphs without some small properly colored subgraphs
- Improved approximation for maximum edge colouring problem
- On the minimum monochromatic or multicolored subgraph partition problems
- An anti-Ramsey theorem on cycles
- Approximation and hardness results for the maximum edge q-coloring problem
- Properly coloured cycles and paths: Results and open problems
- scientific article; zbMATH DE number 3536122 (Why is no real title available?)
- scientific article; zbMATH DE number 3205929 (Why is no real title available?)
- Color degree condition for long rainbow paths in edge-colored graphs
- Rainbow generalizations of Ramsey theory: A survey
- New bounds on the anti-Ramsey numbers of star graphs via maximum edge q-coloring
- Properly colored cycles in edge-colored complete graphs
- Properly colored \(\overrightarrow{C_4} \)'s in arc-colored complete and complete bipartite digraphs
- Rainbow graph splitting
This page was built for publication: Minimal colorings for properly colored subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2563425)
