Perfect matchings in planar cubic graphs
Tóm tắt
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 |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^{{{\left| {V(G)} \right|} \mathord{\left/
{\vphantom {{\left| {V(G)} \right|} {655978752}}} \right.
\kern-\nulldelimiterspace} {655978752}}}$$
perfect matchings.
Tài liệu tham khảo
T. Fowler: Unique Coloring of Planar Graphs, Ph.D. thesis, Georgia Institute of Technology, 1998.
D. Král, J.-S. Sereni and M. Stiebitz: A new lower bound on the number of perfect matchings in cubic graphs, submitted for publication (manuscript 2008).
L. Lovász and M. Plummer: Matching Theory, Annals of Discrete Math. 29, North Holland, Amsterdam, 1986.
A. Schrijver: Counting 1-factors in regular bipartite graphs, J. Combinatorial Theory, Ser. B 72 (1998), 122–135.
H. Whitney: A theorem on graphs, Ann. Math. 32 (1931), 378–390.