Rainbow matching in edge-colored graphs

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

Summary: A rainbow subgraph of an edge-colored graph is a subgraph whose edges have distinct colors. The color degree of a vertex \(v\) is the number of different colors on edges incident to \(v\). \textit{G. Wang} and \textit{H. Li} [``Heterochromatic matchings in edge-colored graphs, Electron. J. Comb. 15, No.\,1, Research Paper R138 (2008; Zbl 1165.05330)] conjectured that for \(k \geqslant 4\), every edge-colored graph with minimum color degree at least \(k\) contains a rainbow matching of size at least \(\lceil k/2\rceil \). We prove the slightly weaker statement that a rainbow matching of size at least \(\lfloor k/2\rfloor\) is guaranteed. We also give sufficient conditions for a rainbow matching of size at least \(\lceil k/2\rceil\) that fail to hold only for finitely many exceptions (for each odd \(k\)).

Recommendations

Cited in

(27)

This page was built for publication: Rainbow matching in edge-colored graphs

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