Premium
Random cubic planar graphs
Author(s) -
Bodirsky Manuel,
Kang Mihyun,
Löffler Mike,
McDiarmid Colin
Publication year - 2006
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20149
Subject(s) - planar , combinatorics , mathematics , random graph , cubic graph , planar graph , random regular graph , struct , cubic form , probabilistic logic , discrete mathematics , cubic crystal system , graph , chordal graph , 1 planar graph , computer science , physics , statistics , condensed matter physics , line graph , voltage graph , programming language , computer graphics (images)
We show that the number of labeled cubic planar graphs on n vertices with n even is asymptotically α n −7/2 ρ − n n !, where ρ −1 ≐ 3.13259 and α are analytic constants. We show also that the chromatic number of a random cubic planar graph that is chosen uniformly at random among all the labeled cubic planar graphs on n vertices is three with probability tending to e −ρ 4 /4!≐ 0.999568 and four with probability tending to 1 − e −ρ 4 /4!as n → ∞ with n even. The proof given combines generating function techniques with probabilistic arguments. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007