Nesta tese apresentamos solu c~oes de dois problemas de colora c~ao de grafos. Para as solu c~oes de ambos problemas, utilizamos ferramentas probabil sticas. Em um desses problemas de colora c~ao, consideramos o espa co de probabilidade Gk n;p dos grafos aleat orios coloridos. Provamos que, para cada k 3, o limiar para a propriedade de que um grafo aleat orio colorido cont em uma arvore geradora propriamente colorida e log n=n, que e precisamente o limiar para a conexidade. Para resolver esse problema, utilizamos uma cota para a cardinalidade de um emparelhamento m aximo em Gn;(1+ ) log n=n, provada por Frieze em 1986. Embora tal cota seja su ciente para resolver esse problema, investigamos o problema da cardinalidade de um emparelhamento m aximo no grafo aleat orio Gn;(1+ ) log n=n e obtivemos um resultado mais preciso. O outro problema de colora c~ao e um problema determin stico, por em, para a solu c~ao deste, utilizamos um resultado de enumera c~ao de grafos cuja demonstra c~ao apresenta argumentos probabil sticos. Dados r t 3 e ` 1, procuramos por grafos com n v ertices que admitem o maior n umero de r-colora c~oes tais que no m aximo t1 cores aparecem pelo menos ` vezes em arestas incidentes a cada v ertice, isto e, r-colora c~oes livres de St;`-arco- ris (estrelas com t` arestas coloridas com t cores distintas tal que cada cor e atribu da a exatamente ` arestas). Para n grande, mostramos que, o grafo completo Kn e o unico grafo extremal. / In this thesis, we obtain solutions for two graph coloring problems, both of which rely on probabilistic tools. In one of these coloring problems, we consider the probability space Gk n;p of edge-colored random graphs. We prove that, for all xed k 3, the threshold for the property that an edge-colored random graph contains a properly colored spanning tree is log n=n, precisely the threshold for connectivity. To solve this problem, we used a bound for the size of a maximum matching in Gn;(1+ ) log n=n, proved by Frieze in 1986. Although such bound is su cient to solve this problem, we investigated the problem of the size of a maximum matching in the random graph Gn;(1+ ) log n=n and we obtained a more precise result. Even though the other coloring problem is deterministic, we used a graph enumeration whose proof is probabilistic. Given r t 3 and ` 1, we look for n-vertex graphs that admit the maximum number of r-edge-colorings such that at most t 1 colors appear at least ` times in edges incident with each vertex, that is, r-edge-colorings avoiding rainbow-St;` (stars with t` edges colored with t distinct colors such that each color is assign to exactly ` edges). For large n, we show that, the complete graph Kn is always the unique extremal graph.
| Identifer | oai:union.ndltd.org:IBICT/oai:lume56.ufrgs.br:10183/153219 |
| Date | January 2016 |
| Creators | Sanches, Juliana |
| Contributors | Hoppen, Carlos |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, instname:Universidade Federal do Rio Grande do Sul, instacron:UFRGS |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0021 seconds