Perfect matchings in planar cubic graphs

Research output: Contribution to journalArticle

8 Scopus citations

Abstract

A well-known conjecture of Lovász 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 {pipe}V (G){pipe}. 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 {pipe}V(G){pipe}/655978752 perfect matchings.

Original languageEnglish (US)
Pages (from-to)403-424
Number of pages22
JournalCombinatorica
Volume32
Issue number4
DOIs
StatePublished - Apr 1 2012

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Perfect matchings in planar cubic graphs'. Together they form a unique fingerprint.

  • Cite this