Random cubic planar graphs.
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 plan...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Published: |
2007
|
| _version_ | 1797098708221820928 |
|---|---|
| author | Bodirsky, M Kang, M Löffler, M McDiarmid, C |
| author_facet | Bodirsky, M Kang, M Löffler, M McDiarmid, C |
| author_sort | Bodirsky, M |
| collection | OXFORD |
| description | 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 techniques with probabilistic arguments. © 2006 Wiley Periodicals, Inc. |
| first_indexed | 2024-03-07T05:13:28Z |
| format | Conference item |
| id | oxford-uuid:dc57a133-b38f-467a-8904-45ac2997f371 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T05:13:28Z |
| publishDate | 2007 |
| record_format | dspace |
| spelling | oxford-uuid:dc57a133-b38f-467a-8904-45ac2997f3712022-03-27T09:17:11ZRandom cubic planar graphs.Conference itemhttp://purl.org/coar/resource_type/c_5794uuid:dc57a133-b38f-467a-8904-45ac2997f371Symplectic Elements at Oxford2007Bodirsky, MKang, MLöffler, MMcDiarmid, CWe 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 techniques with probabilistic arguments. © 2006 Wiley Periodicals, Inc. |
| spellingShingle | Bodirsky, M Kang, M Löffler, M McDiarmid, C Random cubic planar graphs. |
| title | Random cubic planar graphs. |
| title_full | Random cubic planar graphs. |
| title_fullStr | Random cubic planar graphs. |
| title_full_unstemmed | Random cubic planar graphs. |
| title_short | Random cubic planar graphs. |
| title_sort | random cubic planar graphs |
| work_keys_str_mv | AT bodirskym randomcubicplanargraphs AT kangm randomcubicplanargraphs AT lofflerm randomcubicplanargraphs AT mcdiarmidc randomcubicplanargraphs |