✦ LIBER ✦

Extending matchings in planar graphs V

✍ Scribed by Michael D. Plummer

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 473 KB
Volume: 150
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00196-4

No coin nor oath required. For personal study only.

✦ Synopsis

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 and e2 are such that the removal of their endvertices leaves at least one odd component Co. The subgraph G[V(Co) w V(el) w V(e2)] is called a generalized butterfly (or gbutterfly). Clearly, a 2-extendable graph can contain no gbutterfly. The converse, however, is false.

We improve upon a previous result by proving that if G is 4-connected, locally connected and planar with an even number of vertices and has no gbutterfly, it is 2-extendable. Sharpness with respect to the various hypotheses of this result is discussed.

📜 SIMILAR VOLUMES

Extending matchings in planar graphs IV

✍ Michael D. Plummer 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 973 KB

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

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