Rainbow induced subgraphs in proper vertex colorings

Original · EN

For a given graph H we define ρ(H) to be the minimum order of a graph G such that every proper vertex coloring of G contains a rainbow induced subgraph isomorphic to H. We give upper and lower bounds for ρ(H), compute the exact value for some classes of graphs, and consider an interesting combinatorial problem connected with computation of ρ(H) for paths. This research is motivated by some ideas in on-line graph coloring algorithms.