An asymptotic version of the multigraph 1-factorization conjecture

DOI10.1002/JGT.21629MaRDI QIDQ4908822zbMATH OpenOpenAlexWikidataFDO

Authors Emil R. Vaughan

Publication date 7 March 2013

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.5192

zbMATH Keywords

1-factor1-factorizationedge-coloringmultigraph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We give a self-contained proof that for all positive integers $r$ and all $epsilon>0$, there is an integer $N=N(r,epsilon)$ such that for all $ngeN$ any regular multigraph of order $2n$ with multiplicity at most $r$ and degree at least $(1+epsilon)rn$ is 1-factorizable. This generalizes results of Perkovi{'c} and Reed, and Plantholt and Tipnis.

Recommendations

• All regular multigraphs of even order and high degree are 1-factorable
• Factorization of regular multigraphs into regular graphs
• Regular Multigraphs of High Degree are 1-Factorizable
• Semiregular factorizations of regular multigraphs
• Regular multigraphs and their semiregular factorizations

Cites work

• All regular multigraphs of even order and high degree are 1-factorable
• Regular Graphs of High Degree are 1-Factorizable
• Regular Multigraphs of High Degree are 1-Factorizable
• The Solution of a Timetabling Problem

Cited in

(10)

• Graph edge coloring: a survey
• Chromatic index of dense quasirandom graphs
• Extensions of some factorization results from simple graphs to multigraphs
• Factorization of regular multigraphs into regular graphs
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• Edge coloring graphs with large minimum degree
• A note on Hamilton decompositions of even-regular multigraphs
• Total coloring graphs with large maximum degree
• On the multigraph overfull conjecture
• Towards the overfull conjecture

This page was built for publication: An asymptotic version of the multigraph 1-factorization conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4908822)