Random Cubic Planar Graphs
By Manuel Bodirsky, Mike Löffler, Colin McDiarmid, and Mihyun KangRandom Structures and Algorithms, 30 (2007), 78-94
Abstract
We determine the asymptotic number of labeled cubic planar graphs, which grows asymptotically as c n^{-7/2} C^{n} n!, where C and c are analytic constants. The chromatic number of a random cubic planar graph is four with probability tending to 1-e^{-C^{-4}/4!}, and is three with probability tending to e^{-C^{-4}/4!}. The presented proof combines generating function techniques with probabilistic arguments.
English