TAILIEUCHUNG - Báo cáo toán học: "On subgraphs induced by transversals in vertex-partitions of graphs"

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: On subgraphs induced by transversals in vertex-partitions of graphs. | On subgraphs induced by transversals in vertex-partitions of graphs Maria Axenovich Department of Mathematics Iowa State University Ames IA 50011 USA axenovic@ Submitted Mar 18 2005 Accepted Mar 30 2006 Published Apr 4 2006 MR Subject Classifications 05C15 Keywords vertex-colorings Ramsey induced transversals rainbow multicolored Abstract For a fixed graph H on k vertices we investigate the graphs G such that for any partition of the vertices of G into k color classes there is a transversal of that partition inducing H. For every integer k 1 we find a family F of at most six graphs on k vertices such that the following holds. If H 2 F then for any graph G on at least 4k 1 vertices there is a k-coloring of vertices of G avoiding totally multicolored induced subgraphs isomorphic to H. Thus we provide a vertex-induced anti-Ramsey result extending the induced-vertex-Ramsey theorems by Deuber Rodl et al. 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 if all vertices of G have distinct colors. Investigating the existence of monochromatic or rainbow subgraphs isomorphic to H in vertex-colored graphs the following questions naturally arise Question M Can one find a small graph G such that in any vertex-coloring of G with fixed number of colors there is an induced monochromatic subgraph isomorphic to H Question M-R Can one find a small graph G so that any vertex coloring of G contains an induced subgraph isomorphic to H which is either monochromatic or rainbow Question R Can one find a large graph G such that any vertex-coloring of G in a fixed number of colors has a rainbow induced subgraph isomorphic to H THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R36 1 The first two questions are well-studied . 7 8 2 . Together with specific bounds given by Brown and Rodl 3 the following is known Theorem 1 .

• Báo cáo khoa học
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học
• công trình toán học
• Nghiên cứu khoa học
• Phương pháp nghiên cứu khoa học
• Bài giảng Phương pháp nghiên cứu khoa học
• Báo cáo nghiên cứu khoa học
• Trình bày báo cáo nghiên cứu khoa học
• Văn phong sử dụng trong báo cáo khoa học
• Báo cáo khoa học công nghệ
• Đề tài nghiên cứu khoa học
• Nghiên cứu công nghệ làm phân vi sinh
• Báo cáo nghiên cứu phân vi sinh
• Báo cáo tình hình nghiên cứu khoa học
• Mẫu Báo cáo thực hiện nghiên cứu
• Trình bày Báo cáo thực hiện nghiên cứu
• Nội dung Báo cáo thực hiện nghiên cứu
• Hình thức Báo cáo thực hiện nghiên cứu
• Biên bản nghiên cứu khoa học
• Báo cáo khoa học và kỹ thuật
• Đề tài nghiên cứu khoa học y khoa
• Báo cáo nghiên cứu cấp nhà nước
• Nghiên cứu chất lượng chế phẩm thuốc
• Báo cáo nghiên cứu công nghệ sinh học
• Đề tài nghiên cứu thuốc sâu sinh học
• Báo cáo khoa học kỹ thuật
• Báo cáo quản lý chất thải sinh hoạt
• Báo cáo khoa học môi trường
• Nghiên cứu khoa học về môi trường
• Báo cáo nghiên cứu vệ sinh môi trường
• Nghiên cứu tình hình nhiễm độc Cadimi
• Báo cáo chế phẩm sinh học
• Báo cáo nghiên cứu ứng dụng sinh học
• Cách viết báo cáo khoa học
• Quy trình nghiên cứu khoa học
• Báo cáo kết quả nghiên cứu
• báo cáo khoa học
• tuyển tập báo cáo khoa học
• báo cáo ngành toán học
• báo cáo ngành vật lý
• báo cáo ngành chăn nuôi
• Nghiên cứu công nghệ phôi vô tính
• Báo cáo nghiên cứu nông nghiệp
• Báo cáo công nghệ xử lý chất thải
• Báo cáo nghiên cứu khoa học công nghệ
• Kết quả nghiên cứu lúa lai
• Cây lương thực
• Cây thực phẩm
• Một số nguyên tắc nghiên cứu khoa học
• Tiêu chuẩn báo cáo nghiên cứu khoa học
• Nguyên tắc báo cáo khoa học
• Báo cáo nghiên cứu công trình
• Nghiên cứu độ rỗng trong đá chứa dầu khí
• Nghiên cứu công nghệ UV–Fenton
• Nghiên cứu công nghệ xử lý nước thải
• Đề tài y tế đảm bảo an toàn người bệnh
• Báo cáo xây dựng hệ thống y tế
• Kỹ thuật viết báo cáo nghiên cứu
• Viết báo cáo nghiên cứu
• Báo cáo nghiên cứu
• khoa học
• Hình thức soạn thảo văn bản báo cáo
• Báo cáo nghiên cứu nước thải rượu
• Báo cáo công nghệ thiết bị UASB
• Đề tài công nghệ vi sinh
• luận văn mẫu
• người lính việt nam
• sau chiến tranh
• báo cáo ngành triết học
• báo cáo ngành lịch sử
• báo cáo ngành văn học