Rainbow matchings of size m in graphs with total color degree at least 2mn

DOI10.37236/8239zbMATH Open1444.05057arXiv1810.05324OpenAlexW3045784041MaRDI QIDQ783076FDOQ783076

Authors: Jürgen Kritschgau 

Publication date: 30 July 2020

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: The existence of a rainbow matching given a minimum color degree, proper coloring, or triangle-free host graph has been studied extensively. This paper, generalizes these problems to edge colored graphs with given total color degree. In particular, we find that if a graph $G$ has total color degree $2mn$ and satisfies some other properties, then $G$ contains a matching of size $m$; These other properties include $G$ being triangle-free, $C_4$-free, properly colored, or large enough.

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

Recommendations

• Rainbow matchings of size \(\delta(G)\) in properly edge-colored graphs
• Rainbow matchings in properly colored multigraphs
• Rainbow matchings in properly colored bipartite graphs
• A rainbow \(k\)-matching in the complete graph with \(r\) colors
• Large rainbow matchings in edge-colored graphs with given average color degree
• Rainbow matchings in properly edge colored graphs
• Rainbow matchings in properly-colored hypergraphs
• Existence of rainbow matchings in properly edge-colored graphs
• Large rainbow matchings in edge-coloured graphs
• A note on large rainbow matchings in edge-coloured graphs

zbMATH Keywords

edge colored graphs with given total color degree

Mathematics Subject Classification ID

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

Cites Work

• Transversals of latin squares and their generalizations
• Heterochromatic matchings in edge-colored graphs
• Large rainbow matchings in edge-coloured graphs
• Rainbow matching in edge-colored graphs
• Rainbow matchings and cycle-free partial transversals of Latin squares
• Rainbow matchings of size \(\delta(G)\) in properly edge-colored graphs
• A note on large rainbow matchings in edge-coloured graphs
• Existence of rainbow matchings in properly edge-colored graphs

Cited In (2)

• Large rainbow matchings in edge-colored graphs with given average color degree
• A rainbow \(k\)-matching in the complete graph with \(r\) colors

This page was built for publication: Rainbow matchings of size \(m\) in graphs with total color degree at least \(2mn\)

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