Conference item icon

Conference item

Random cubic planar graphs.

Abstract:

We show that the number of labeled cubic planar graphs on n vertices with n even is asymptotically αn-7/2 ρ-nn!, 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 t...

Expand abstract
Publication status:
Published

Actions


Access Document


Publisher copy:
10.1002/rsa.20149

Authors


Volume:
30
Issue:
1-2
Pages:
78-94
Host title:
Random Struct. Algorithms
Publication date:
2007-01-01
DOI:
EISSN:
1098-2418
ISSN:
1042-9832
Source identifiers:
102289
Keywords:
Pubs id:
pubs:102289
UUID:
uuid:dc57a133-b38f-467a-8904-45ac2997f371
Local pid:
pubs:102289
Deposit date:
2012-12-19

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP