Monochromatic partitions in random graphs

Abstract

En 1991 Erdos, Gyárfás y Pyber conjeturaron que para todo r-coloreo de un grafo completo Kn este puede ser particionado en a lo más r - 1 árboles monocromáticos. Paralelamente Gyárfás y Lehel conjeturaron un resultado similar para un tipo diferente de grafos. Ellos propusieron que para todo r-coloreo de las aristas de un grafo bipartito completo este puede ser cubierto por a lo más 2r - 2 árboles monocromáticos. En 2017 Bal y DeBiasio fueron los primeros en estudiar este problema para grafos aleatorios G(n,p) en G_(n,p) y conjeturaron que si p >> (r log(n)/n)^(1/r) entonces G(n,p) puede ser particionado,casi seguramente, por a lo más r árboles monocromáticos. En esta memoria proponemos una version de este problema para grafos bipartitos aleatorios en el caso r = 2. Conjeturamos que para la misma cota de p podemos, casi seguramente, particionar G en B_(n,n,p) por a lo más 3 árboles monocromáticos. Además, probamos esta conjetura aproximadamente. Finalmente, damos un ejemplo de un 2-coloreo de las aristas tal que, casi seguramente, necesitamos al menos tres árboles monocromáticos para particionar el grafo, y por lo tanto, nuestra conjetura sería mejor posible.