Rainbow Induced Subgraphs in Proper Vertex Colorings

Article type: Research Article

Authors: Kisielewicz, Andrzej | Szykuła, Marek

Affiliations: University of Wrocław, Department of Mathematics and Computer Science, pl. Grunwaldzki 2, 50-384 Wrocław, Poland. andrzej.kisielewicz@math.uni.wroc.pl; marek.szykula@ii.uni.wroc.pl

Note: [] Supported in part by Polish MNiSW grant N N201 543038. Address for correspondence: University of Wrocław, Department of Mathematics and Computer Science, pl. Grunwaldzki 2, 50-384 Wrocław, Poland

Abstract: Given a 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. 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.

Keywords: rainbow, induced subgraph, vertex coloring, replication graph, C++

DOI: 10.3233/FI-2011-572

Journal: Fundamenta Informaticae, vol. 111, no. 4, pp. 437-451, 2011