To refer to this page use:
http://arks.princeton.edu/ark:/88435/pr1ht1d
Abstract: | A well-known conjecture of Lovasz and Plummer from the mid-1970’s, still open, asserts that for every cubic graph G with no cutedge, the number of perfect matchings in G is exponential in |V (G)|. In this paper we prove the conjecture for planar graphs; we prove that if G is a planar cubic graph with no cutedge, then G has at least 2(|V(G)|/655978752) perfect matchings. |
Publication Date: | Apr-2012 |
Electronic Publication Date: | 2-Sep-2012 |
Citation: | Chudnovsky, Maria, Seymour, Paul. (2012). Perfect matchings in planar cubic graphs. COMBINATORICA, 32 (403 - 424. doi:10.1007/s00493-012-2660-9 |
DOI: | doi:10.1007/s00493-012-2660-9 |
ISSN: | 0209-9683 |
Pages: | 403 - 424 |
Type of Material: | Journal Article |
Journal/Proceeding Title: | COMBINATORICA |
Version: | Author's manuscript |
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.