✦ LIBER ✦

Extending matchings in planar graphs IV

✍ Scribed by Michael D. Plummer

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 973 KB
Volume: 109
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90292-n

No coin nor oath required. For personal study only.

✦ Synopsis

Plummer, M.D., Extending matchings in planar graphs IV, Discrete Mathematics 109 (1992) 207-219. The structure of certain non-Zextendable planar graphs is studied first. In particular, 4-connected S-regular planar graphs which are not 2-extendable are investigated and examples of these are presented.

It is then proved that all 5-connected even planar graphs are 2-extendable.

Finally, a certain configuration called a generalized buttefly is defined and it is shown that 4-connected maximal planar even graphs which contain no generalized butterfly are 2-extendable.

📜 SIMILAR VOLUMES

Extending matchings in planar graphs V

✍ Michael D. Plummer 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 473 KB

A graph G on at least 2n + 2 vertices in n-extendable if every set of n independent edges extends to (i.e., is a subset of) a perfect matching in G. It is known that no planar graph is 3-extendable. In the present paper we continue to study 2-extendability in the plane. Suppose independent edges el

Extending matchings in claw-free graphs

✍ Michael D. Plummer 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 506 KB

Let G be a graph with a perfect matching and let n be an integer, has a perfect matching for every pair of points u and v in V(G). It is proved that every 3-connected claw-free graph is bicritical and for n>2, every (2n+ l)-connected claw-free graph is n-extendable. Matching extension in planar an

Induced matching extendable graphs

✍ Jinjiang, Yuan 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 261 KB

We say that a simple graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. The main results of this paper are as follows: (1) For every connected IM-extendable graph 2 |V (G)| -2; the equality holds if and only if G ∼

Extending colorings of locally planar gr

Extending colorings of locally planar graphs

✍ Michael O. Albertson; Joan P. Hutchinson 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB 👁 1 views

Suppose G is a graph embedded in S g with width (also known as edge width) at least 264(2 g À 1). If P V(G) is such that the distance between any two vertices in P is at least 16, then any 5-coloring of P extends to a 5-coloring of all of G. We present similar extension theorems for 6-and 7-chromati

Counting Matchings in Graphs

✍ E.J. Farrell 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 488 KB

A general formula is derivedfor the matching polynomial of an arbitrary graph G. This yields a methodfor counting matchings in graphs. From the general formula, explicit formulae are deducedfor the number of k-matchings in several well-known families of graphs.

Matchings in polytopal graphs

✍ B. Grünbaum 📂 Article 📅 1974 🏛 John Wiley and Sons 🌐 English ⚖ 667 KB