TAILIEUCHUNG - Báo cáo toán học: "Critical subgraphs of a random graph"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Critical subgraphs of a random graph. | Critical subgraphs of a random graph Michael Molloy Department of Computer Science University of Toronto Toronto Canada molloy@ Bruce Reed Equipe Combinatoire CNRS Universite Pierre et Marie Curie Paris France reed@ Submitted Sept 7 1998 Accepted Sept 6 1999. Abstract We prove that the threshold for a random graph to have a k-core is equal to the threshold for having a subgraph which meets a necessary condition of Gallai for being k-critical. 1991 Mathematics Subject Classification Primary 05C80 Secondary 05C15. 1 Introduction In this paper we examine the random graph Gn M formed by taking n vertices and choosing M edges where each of the M possible edgesets is equally likely to be chosen. In particular we will be concerned with the chromatic number of such a graph when M O n . Equivalently we often discuss the random graph process in which we start with the graph with n vertices and no edges and repeatedly add an edge chosen uniformly at random from amongst all edges not currently present. Note that Gn M is equivalent to the state of the random graph process after exactly M iterations. One of the most tantalizing open problems in random graph theory see for example 11 is that of determining dk sup d G iM dn kg where y G is the chromatic number of G. As is the trend in the study of k-chromatic graphs the case k 2 is well-understood - d2 0 - while the case k 3 seems much 1We say that Gn p almost surely . has a property P if limn 1 Pr G P has Pg 1. 1 THE ELECTRONIC .JOURNAL OF COmBINATORICS 6 1999 R35 2 more difficult. In fact it was only recently shown that for k 3 the threshold for k-colourability is sharp see 1 and 14 . If G is not k-colourable then it must have a k 1 -critical subgraph . a subgraph H c G such that x H k 1 but x H e k for any edge e 2 E G . The most well known necessary conditions for a graph to be k 1 -critical are see 9 a it must have minimum degree at most k b it must be 2-connected. Often a property P

• 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