Nós consideramos o seguinte problema. Fixado um grafo H e um número real \\alpha \\in (0,1], determine o menor \\beta = \\beta(\\alpha, H) que satisfaz a seguinte propriedade: se G é um grafo de ordem n no qual cada subconjunto de [\\alpha n] vértices induz mais que \\beta n^2 arestas então G contém H como subgrafo. Este problema foi iniciado e motivado por Erdös ao conjecturar que todo grafo livre de triângulo de ordem n contém um subconjunto de [n/2] vértices que induz no máximo n^2 /50 arestas. Nosso resultado principal mostra que i) todo grafo de ordem n livre de triângulos e pentágonos contém um subconjunto de [n/2] vértices que induz no máximo n^2 /64 arestas, e ii) se G é um grafo regular de ordem n livre de triângulo, com grau excedendo n/3, então G contém um subconjunto de [n/2] vértices que induz no máximo n^2 /50 arestas. Se além disso G não é 3-cromático então G contém um subconjunto de [n/2] vértices que induz menos de n^2 /54 arestas. Como subproduto e confirmando uma conjectura de Erdös assintoticamente, temos que todo grafo regular de ordem n livre de triângulo com grau excedendo n/3 pode ser tornado bipartido pela omissão de no máximo (1/25 + o(1))n^2 arestas. Nós também fornecemos um contraexemplo a uma conjectura de Erdös, Faudree, Rousseau e Schelp. / We consider the following problem. Fixed a graph H and a real number \\alpha \\in (0,1], determine the smallest \\beta = \\beta(\\alpha, H) satisfying the following property: if G is a graph of order n such that every subset of [\\alpha n] vertices spans more that \\beta n^2 edges then G contains H as a subgraph. This problem was initiated and motivated by Erdös who conjectured that every triangle-free graph of order n contains a subset of [n/2] vertices that spans at most n^2 /50 edges. Our main result shows that i) every triangle- and pentagon-free graph of order n contains a subset of [n/2] vertices inducing at most n^2 /64 edges and, ii) if G is a triangle-free regular graph of order n with degree exceeding n/3 then G contains a subset of [n/2] vertices inducing at most n^2 /50 edges. Furthermore, if G is not 3-chromatic then G contains a subset of [n/2] vertices inducing less than n^2 /54 edges. As a by-product and confirming a conjecture of Erdös asymptotically, we obtain that every n-vertex triangle-free regular graph with degree exceeding n/3 can be made bipartite by removing at most (1/25 + o(1))n^2 edges. We also provide a counterexample to a conjecture of Erdös, Faudree, Rousseau and Schelp.
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-15032019-114236 |
| Date | 14 November 2018 |
| Creators | Fernandez, Luis Eduardo Zambrano |
| Contributors | Kohayakawa, Yoshiharu |
| Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| Source Sets | Universidade de São Paulo |
| Language | Portuguese |
| Detected Language | English |
| Type | Tese de Doutorado |
| Format | application/pdf |
| Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0015 seconds