𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An Asymptotic Version of the Multigraph 1-Factorization Conjecture

✍ Scribed by E. R. Vaughan

Publisher
John Wiley and Sons
Year
2012
Tongue
English
Weight
504 KB
Volume
72
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We give a self‐contained proof that for all positive integers r and all , there is an integer such that for all any regular multigraph of order 2__n__ with multiplicity at most r and degree at least is 1‐factorizable. This generalizes results of PerkoviΔ‡ and Reed (Discrete Math 165/166 (1997), 567–578) and Plantholt and Tipnis (J London Math Soc 44 (1991), 393–400).

πŸ“œ SIMILAR VOLUMES

An asymptotic version of a conjecture by
An asymptotic version of a conjecture by Enomoto and Ota
✍ Colton Magnant; Daniel M. Martin πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 172 KB

## Abstract In 2000, Enomoto and Ota [J Graph Theory 34 (2000), 163–169] stated the following conjecture. Let __G__ be a graph of order __n__, and let __n__~1~, __n__~2~, …, __n__~__k__~ be positive integers with . If Οƒ~2~(__G__)β‰₯__n__+ __k__βˆ’1, then for any __k__ distinct vertices __x__~1~, __x__~

An Equivalent Version of the 3-Flow Conj
An Equivalent Version of the 3-Flow Conjecture
✍ Martin Kochol πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 88 KB

The 3-flow conjecture of Tutte is that every bridgeless graph without a 3-edge cut has a nowhere-zero 3-flow. We show that it suffices to prove this conjecture for 5-edge-connected graphs.

Constructing indecomposable 1-factorizat
Constructing indecomposable 1-factorizations of the complete multigraph
✍ Dan Archdeacon; Jeffrey H. Dinitz πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 762 KB

Archdeacon, D. and J.H. Dinitz. Constructing indecomposable I-factorizations of the complete multigraph, Discrete Mathematics 92 (1991) 9-19.

Lenstraβ€²s Proof of the Carlitz-Wan Conje
Lenstraβ€²s Proof of the Carlitz-Wan Conjecture on Exceptional Polynomials: An Elementary Version
✍ S.D. Cohen; M.D. Fried πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 167 KB

We give a proof, following an argument of Lenstra, of the conjecture of Carlitz (1966) as generalized by Wan (1993). This says that there are no exceptional polynomials of degree \(n\) over \(\mathbb{F}_{q}\) if \((n, q-1)>1\). Fried, Guralnick, and Saxl previously proved Carlitz's conjecture: there

The upper bound theorem for polytopes: a
The upper bound theorem for polytopes: an easy proof of its asymptotic version
✍ Raimund Seidel πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 128 KB

Since at least half of the d edges incident to a vertex u of a simple d-polytope P either all point "up" or all point "down," v must be the unique "bottom" or "top" vertex of a face of P of dimension at least d/2. Thus the number of P's vertices is at most twice the number of such high-dimensional f