Monochromatic and heterochromatic subgraph problems in a randomly colored graph

DOI10.1007/S00373-008-0789-5arXiv0711.3827WikidataQ105583341 ScholiaQ105583341MaRDI QIDQ6207597

Mikio Kano, Xueliang Li

Publication date: 24 November 2007

Abstract: Let $K_n$ be the complete graph with $n$ vertices and $c_1,c_2,...,c_r$ be $r$ different colors. Suppose we randomly and uniformly color the edges of $K_n$ in $c_1,c_2,...,c_r$. Then we get a random graph, denoted by $mathcal{K}_n^r$. In the paper, we investigate the asymptotic properties of several kinds of monochromatic and heterochromatic subgraphs in $mathcal{K}_n^r$. Accurate threshold functions in some cases are also obtained.

Mathematics Subject Classification ID

Trees (05C05) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02)

This page was built for publication: Monochromatic and heterochromatic subgraph problems in a randomly colored graph

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