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

DOI10.37236/8239MaRDI QIDQ783076zbMATH OpenOpenAlexFDO

Authors Jürgen Kritschgau

Publication date 30 July 2020

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

• A note on large rainbow matchings in edge-coloured graphs
• Existence of rainbow matchings in properly edge-colored graphs
• 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
• Transversals of latin squares and their generalizations

Cited in

(2)

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

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)