tailieunhanh - 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