Skip to main content

Perfect matchings in planar cubic graphs

Author(s): Chudnovsky, Maria; Seymour, Paul D.

To refer to this page use:
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.