| Texto completo | |
| Autor(es): |
Marciniszyn‚ M.
;
Skokan‚ J.
;
Spöhel‚ R.
;
Steger‚ A.
Número total de Autores: 4
|
| Tipo de documento: | Artigo Científico |
| Fonte: | RANDOM STRUCTURES & ALGORITHMS; v. 34, n. 4, p. 419-453, 2009. |
| Resumo | |
Consider the following problem: Forgiven graphs G and F-1,..., F-k, find a coloring of the edges of G with k colors such that G does not contain F; in color i. Rodl and Rucinski studied this problem for the random graph G,,, in the symmetric case when k is fixed and F-1 = ... = F-k = F. They proved that such a coloring exists asymptotically almost surely (a.a.s.) provided that p <= bn(-beta) for some constants b = b(F,k) and beta = beta(F). This result is essentially best possible because for p >= Bn-beta, where B = B(F, k) is a large constant, such an edge-coloring does not exist. Kohayakawa and Kreuter conjectured a threshold function n(-beta(F1,..., Fk)) for arbitrary F-1, ..., F-k. In this article we address the case when F-1,..., F-k are cliques of different sizes and propose an algorithm that a.a.s. finds a valid k-edge-coloring of G(n,p) with p <= bn(-beta) for some constant b = b(F-1,..., F-k), where beta = beta(F-1,..., F-k) as conjectured. With a few exceptions, this algorithm also works in the general symmetric case. We also show that there exists a constant B = B(F,,..., Fk) such that for p >= Bn-beta the random graph G(n,p) a.a.s. does not have a valid k-edge-coloring provided the so-called KLR-conjecture holds. (C) 2008 Wiley Periodicals, Inc. Random Struct. Alg., 34, 419-453, 2009 (AU) | |
| Processo FAPESP: | 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas |
| Beneficiário: | Yoshiharu Kohayakawa |
| Modalidade de apoio: | Auxílio à Pesquisa - Programa PRONEX - Temático |
| Processo FAPESP: | 04/15397-4 - Aplicacoes de quase-aleatoriedade em combinatoria. |
| Beneficiário: | Jozef Skokan |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |