Abstract | ||
---|---|---|
We show that the number of labeled cubic planar graphs on nvertices with n even is asymptoticallyαn-7/2ρ-nn!,where ρ-1 ... 3.13259 and α are analyticconstants. We show also that the chromatic number of a random cubicplanar graph that is chosen uniformly at random among all thelabeled cubic planar graphs on n vertices is three withprobability tending to e-ρ4/4! ... 0.999568and four with probability tending to 1 -e-ρ4/4! as n → ∞ withn even. The proof given combines generating functiontechniques with probabilistic arguments. © 2006 WileyPeriodicals, Inc. Random Struct. Alg., 2007 |
Year | DOI | Venue |
---|---|---|
2007 | 10.1002/rsa.v30:1/2 | Random Struct. Algorithms |
Keywords | Field | DocType |
planar graph,connectedness | Discrete mathematics,Wheel graph,Random regular graph,Combinatorics,Random graph,Polyhedral graph,Chordal graph,Planar straight-line graph,Nowhere-zero flow,Book embedding,Mathematics | Journal |
Volume | Issue | Citations |
30 | 1-2 | 15 |
PageRank | References | Authors |
1.23 | 12 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Manuel Bodirsky | 1 | 644 | 54.63 |
Mihyun Kang | 2 | 163 | 29.18 |
Mike Löffler | 3 | 15 | 1.23 |
Colin McDiarmid | 4 | 1071 | 167.05 |