Rainbow Coloring of Random Graphs
Chenlong Lin
Longyan University/INTI International University
Goh KhangWen
INTI International University
Jinshan Xie
Longyan University
DOI: https://doi.org/10.59429/esta.v11i3.7344
Keywords: Random graphs; Rainbow coloring; Probability method
Abstract
This paper explores the issue of identifying rainbow embeddings within random graphs, which occur when all the edges of a subgraph are colored distinctly. Using probabilistic methods, we investigate the conditions under which a random graph contains such an embedding. Specifically, for a specified graph H, when p is greater than the threshold, randomly select a color from the set of colors c to color the edges of graph G, then with high probability graph G contains a rainbow copy of H. These results provide new insights into the interplay between random graph theory and edge coloring, with potential applications in areas such as network design and combinatorics.
References
[1] J. A. Bondy, U. S. R. Murty, Graph theory, Graduates Texts in Mathematics, Springer 2008.
[2] A. Ferber, R. Nenadov, U. Peter. Universality of random graphs and rainbow embedding[J]. Random Structures & Algorithms, 2016, 48(3):546-564. [3] A. Frieze, P. Loh, Rainbow Hamilton cycles in random graphs, Random Struct Algorithms 44 (2014) 328–354.
[4] C. Cooper, A. Frieze, Multi-coloured Hamilton cycles in random edge-coloured graphs, Comb. Probab. Comput. 11 (2002) 129–133.
[5] S. Janson, T. Luczak T, A. Ruciński. Random Graphs[M]. New York:Wiley, 2000:26-27.
[6] R. B. Mallion, The six (or seven) bridges of Kaliningrad: a personal Eulerian walk, MATCH Communications in Mathematical and in Computer Chemistry 58 (2007) 529–556.
[7] D. B. West, Introduction to graph theory, China Machine Press, 2001.