A note on randomly colored matchings in random bipartite graphs

DOI10.1007/978-3-030-55857-4_8MaRDI QIDQ2232034zbMATH OpenOpenAlexFDO

Authors Alan Frieze

Publication date 4 October 2021

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

zbMATH Keywords

perfect matchingmatching color profile

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We are given a bipartite graph that contains at least one perfect matching and where each edge is colored from a set $Q=c_1,c_2,ldots,c_q$. Let $Q_i=seteinE(G):c(e)=c_i$, where $c(e)$ denotes the color of $e$. The perfect matching color profile $mcp(G)$ is defined to be the set of vectors $(m_1,m_2,ldots,m_q)in[n{]}^q$ such that there exists a perfect matching $M$ such that $|Mcap{Q}_i|=m_i$. We give bounds on the matching color profile for a randomly colored random bipartite graph.

Recommendations

• The threshold for the full perfect matching color profile in a random coloring of random graphs
• Rainbow matchings: existence and counting
• Rainbow perfect matchings in complete bipartite graphs: existence and counting
• Rainbow perfect matchings in \(r\)-partite graph structures
• Existence of a perfect matching in a random (\(1+e^{-1}\))-out bipartite graph

Cited in

(6)

• The threshold for the full perfect matching color profile in a random coloring of random graphs
• Random Bichromatic Matchings
• Colorful Hamilton Cycles in Random Graphs
• The normalized matching property in random and pseudorandom bipartite graphs
• Randomly Coloring Regular Bipartite Graphs and Graphs with Bounded Common Neighbors
• Matchings in colored bipartite networks

This page was built for publication: A note on randomly colored matchings in random bipartite graphs

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