Rainbow induced subgraphs in proper vertex colorings

Details Rainbow induced subgraphs in proper vertex colorings Rainbow induced subgraphs in proper vertex colorings

2011-05-18

arxiv.org/abs/1105.3712v1

Mathematics

Combinatorics

Scientific paper

For a given 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. This research is motivated by some ideas in on-line graph coloring algorithms.

Affiliated with

Also associated with

No associations

Rating

Rainbow induced subgraphs in proper vertex colorings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Rainbow induced subgraphs in proper vertex colorings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rainbow induced subgraphs in proper vertex colorings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-54609