tailieunhanh - Báo cáo toán học: "Avoiding rainbow induced subgraphs in vertex-colorings"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Avoiding rainbow induced subgraphs in vertex-colorings. | Avoiding rainbow induced subgraphs in vertex-colorings Maria Axenovich and Ryan Martin Department of Mathematics Iowa State University Ames IA 50011 axenovic@ rymartin@ Submitted Jun 25 2007 Accepted Jan 4 2008 Published Jan 14 2008 Mathematics Subject Classification 05C15 05C55 Abstract For a fixed graph H on k vertices and a graph G on at least k vertices we write G H if in any vertex-coloring of G with k colors there is an induced subgraph isomorphic to H whose vertices have distinct colors. In other words if G H then a totally multicolored induced copy of H is unavoidable in any vertex-coloring of G with k colors. In this paper we show that with a few notable exceptions for any graph H on k vertices and for any graph G which is not isomorphic to H G-yG H. We explicitly describe all exceptional cases. This determines the induced vertex-anti-Ramsey number for all graphs and shows that totally multicolored induced subgraphs are in most cases easily avoidable. 1 Introduction Let G V E be a graph. Let c V G k be a vertex-coloring of G. We say that G is monochromatic under c if all vertices have the same color and we say that G is rainbow or totally multicolored under c if all vertices of G have distinct colors. The existence of a graph forcing an induced monochromatic subgraph isomorphic to H is well known. The following bounds are due to Brown and Rodl Theorem 1 Vertex-Induced Graph Ramsey Theorem 6 For all graphs H and all positive integers t there exists a graph Rt H such that if the vertices of Rt H are colored with t colors then there is an induced subgraph of Rt H isomorphic to H which is monochromatic. Let the order of Rt H with smallest number of vertices be rmono t H . Then there are constants C1 C1 t C2 C2 t such that C1k2 max rmono t H V H kg C2k2 log2 k. Research supported in part by NSA grant H98230-05-1-0257 THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R12 1 Theorem 1 is one of numerous vertex-Ramsey results investigating the .