Rainbow Induced Subgraphs in Proper Vertex Colorings
Given a graph H we define rho(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 rho(H), compute the exact value for some classes of graphs, and consider an interesting combinatorial problem connected with computation of rho(H) for paths. A part of this research has been guided by a computer search and, accordingly, some computational results are presented. A special motivation comes from research in on-line coloring.
rainbow induced subgraph vertex coloring replication graph c plus