Perfect matchings in planar cubic graphs

Research output: Contribution to journalArticle

7 Citations (Scopus)

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

Fingerprint

Cubic Graph
Perfect Matching
Planar graph
Pipe

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Discrete Mathematics and Combinatorics

Cite this

@article{d7f2d4da38ad474491c2ba7bb6391040,
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 Seymour, {Paul Douglas}",
year = "2012",
month = "4",
day = "1",
doi = "https://doi.org/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",

}

Perfect matchings in planar cubic graphs. / Chudnovsky, Maria; Seymour, Paul Douglas.

In: Combinatorica, Vol. 32, No. 4, 01.04.2012, p. 403-424.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Perfect matchings in planar cubic graphs

AU - Chudnovsky, Maria

AU - Seymour, Paul Douglas

PY - 2012/4/1

Y1 - 2012/4/1

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 - http://www.scopus.com/inward/record.url?scp=84865804944&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84865804944&partnerID=8YFLogxK

U2 - https://doi.org/10.1007/s00493-012-2660-9

DO - https://doi.org/10.1007/s00493-012-2660-9

M3 - Article

VL - 32

SP - 403

EP - 424

JO - Combinatorica

JF - Combinatorica

SN - 0209-9683

IS - 4

ER -