Heterochromatic matchings in edge-colored graphs
Summary: Let \(G\) be an (edge-)colored graph. A heterochromatic matching of \(G\) is a matching in which no two edges have the same color. For a vertex \(v\), let \(d^c(v)\) be the color degree of \(v\). We show that if \(d^c(v)\geq k\) for every vertex \(v\) of \(G\), then \(G\) has a heterochromatic matching of size \(\big\lceil{5k-3\over 12}\big\rceil\). For a colored bipartite graph with bipartition \((X,Y)\), we prove that if it satisfies a Hall-like condition, then it has a heterochromatic matching of cardinality \(\big\lceil{|X|\over 2}\big\rceil\), and we show that this bound is best possible.
- Color degree and heterochromatic matchings in edge-colored bipartite graphs
- scientific article; zbMATH DE number 5914945
- Sufficient Conditions for the Existence of Perfect Heterochromatic Matchings in Colored Graphs
- Maximum heterochromatic matchings in complete bipartite graph \(K_{n,m}\) and complete graph \(K_{2n}\)
- The heterochromatic cycles in edge-colored graphs
- A note on rainbow matchings in strongly edge-colored graphs
- Uniquely restricted matchings and edge colorings
- Existence of rainbow matchings in properly edge-colored graphs
- A note on heterochromatic \(C_4\) in edge-colored triangle-free graphs
- Large rainbow matchings in edge-colored graphs with given average color degree
- Quadratic vertex kernel for rainbow matching
- Matchings with few colors in colored complete graphs and hypergraphs
- Rainbow matchings in strongly edge-colored graphs
- Orthogonal matchings revisited
- Existences of rainbow matchings and rainbow matching covers
- f-class two graphs whose f-cores have maximum degree two
- Rainbow \(C_4\)'s and directed \(C_4\)'s: the bipartite case study
- Maximum heterochromatic matchings in complete bipartite graph \(K_{n,m}\) and complete graph \(K_{2n}\)
- Existence of rainbow matchings in strongly edge-colored graphs
- scientific article; zbMATH DE number 5914945 (Why is no real title available?)
- Sufficient Conditions for the Existence of Perfect Heterochromatic Matchings in Colored Graphs
- Color degree and heterochromatic matchings in edge-colored bipartite graphs
- Rainbow edge-coloring and rainbow domination
- A note on large rainbow matchings in edge-coloured graphs
- Rainbow matchings of size m in graphs with total color degree at least 2mn
This page was built for publication: Heterochromatic matchings in edge-colored graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010874)
