Perfect matchings in planar cubic graphs

Maria Chudnovsky; Paul Seymour

doi:10.1007/s00493-012-2660-9

Perfect matchings in planar cubic graphs

Mathematics

Research output: Contribution to journal › Article › peer-review

14 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 language	English (US)
Pages (from-to)	403-424
Number of pages	22
Journal	Combinatorica
Volume	32
Issue number	4
DOIs	https://doi.org/10.1007/s00493-012-2660-9
State	Published - Apr 2012

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s00493-012-2660-9

Cite this

@article{564ea4d8c9b34e79bd06643d38d1b236,

title = "Perfect matchings in planar cubic graphs",

abstract = "A well-known conjecture of Lov{\'a}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.",

author = "Maria Chudnovsky and Paul Seymour",

note = "Funding Information: ∗ This research was conducted while the author served as a Clay Mathematics Institute Research Fellow. † Supported by ONR grant N00014-01-1-0608 and NSF grant DMS-0070912. 1 Note added in proof: The full conjecture by Lov{\'a}sz and Plummer has now been solved, in the following paper: L. Esperet, F. Kardos, A. King, D. Kr{\'a}l, and S. Norine, “Exponentially many perfect matchings in cubic graphs”, Advances in Mathematics 227 (2011), 1646–1664.",

year = "2012",

month = apr,

doi = "10.1007/s00493-012-2660-9",

language = "English (US)",

volume = "32",

pages = "403--424",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "4",

}

TY - JOUR

T1 - Perfect matchings in planar cubic graphs

AU - Chudnovsky, Maria

AU - Seymour, Paul

N1 - Funding Information: ∗ This research was conducted while the author served as a Clay Mathematics Institute Research Fellow. † Supported by ONR grant N00014-01-1-0608 and NSF grant DMS-0070912. 1 Note added in proof: The full conjecture by Lovász and Plummer has now been solved, in the following paper: L. Esperet, F. Kardos, A. King, D. Král, and S. Norine, “Exponentially many perfect matchings in cubic graphs”, Advances in Mathematics 227 (2011), 1646–1664.

PY - 2012/4

Y1 - 2012/4

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/84865804944

UR - https://www.scopus.com/pages/publications/84865804944#tab=citedBy

U2 - 10.1007/s00493-012-2660-9

DO - 10.1007/s00493-012-2660-9

M3 - Article

AN - SCOPUS:84865804944

SN - 0209-9683

VL - 32

SP - 403

EP - 424

JO - Combinatorica

JF - Combinatorica

IS - 4

ER -

Perfect matchings in planar cubic graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this