• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Master's Dissertation
DOI
https://doi.org/10.11606/D.45.2000.tde-20220712-115125
Document
Author
Full name
Marcio Grossi de Almeida
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2000
Supervisor
Title in Portuguese
Números de Ramsey induzidos e semi-induzidos
Keywords in Portuguese
Combinatória
Teoria Dos Grafos
Abstract in Portuguese
Dados dois grafos G e H quaisquer, chamamos de número de Ramsey semi-induzido `r sind(G,H)¦ e de número de Ramsey semi-induzido para arestas `r sind(G,H)¦, respectivamente, a menor ordem e o menor número de arestas possíveis para um grafo`GAMA¦com a propriedade de que sempre que suas arestas são coloridas com as cores vermelha e azul, ou `GAMA¦ possui uma cópia vermelha de G ou `GAMA¦ possui uma cópia induzida de H. Para o caso em que T é uma árvore e H é um grafo qualquer, nósmostramos que `r sind(T,H)¦< OU = `(t-1)`h POT.2¦ e `r sind(T,H)¦< OU = `[(t-1)h] POT.2[E(H)], se h=[V(H)] > OU = 2 e t=[V(T)] > OU =2. No caso em que T possui grau máximo limitado, nós mostramos que, para todo E > 0, se h=[V(H)] > OU =`0SOB.0¦(E), t=[V(T)] > OU = `0 SOB.t¦(E) e d=¦DELTA¦(T) então `r sind(T,H) < `cd POT.9/2¦(`h POT.2¦ `t POT.3/2¦)`POT.1+E[E(H¦)], onde c é uma constante que depende de E. Nós também investigamos o número de Ramsey induzido `r ind(G,H)¦, que édefinido como sendo a menor ordem possível para um grafo `GAMA¦ com a propriedade de que sempre que suas arestas são coloridas com as cores vermelha e azul, ou `GAMA¦ possui uma cópia vermelha induzida de G ou `GAMA¦ possui uma cópia azulinduzida de H. Nós mostramos que se o grafo G pertence à classe `EH POT.var¦({`K POT.1¦, `K POT.2¦, `I POT.2¦}) - que equivale à classe dos grafos simples definida em Erdos e Hajnal [5] - então `r ind(G,H) < [V(H)] POT.f¦, onde f é uma constanteque depende somente de G
Title in English
not available
Abstract in English
For any given graphs G and H, we define the semi-induced Ramsey number r sind(G,H) and the edge semi-induced Ramsey number r sind(G,H), as the smallest order and the smallest number of edges of a graph `GAMA¦ having the property that, wheneveritsedges are coloured red and blue, either a red copy of G arises or else a blue induced copy of H arises. When T is a tree and H is a graph, we show that r ind (T,H) < OU = (t-1)¦h POT.2¦ and r sind(T,H) < OU = [(t-1)h] POT.2[E(H)], where h=[V(H)] > ou = 2 and t = [V(T)] > OU = 2. When T has bounded maximum degree, we show that, for any E > 0, if we have h = [V(H)] > OU = `0 SOB. h¦(E), t=[V(T)] > OU = `0 SOB.t¦ (E) and d = `DELTA¦(T) then r sind(T,H) < `cd POT.9/2¦(`hPOT.2¦tPOT.3/2¦)`POT.1=E¦[E(H)], where c is a constant that only depends on E. We also investigate the induced Ramsey number r ind(G,H), which is defined as the smallest order of a graph `GAMA¦ having the property that, whenever its edges arecolouredred and blue, either a red induced copy of G arises or else a blue induced copy of H arises. We show that if G belongs to a class of graphs called `EH POT.var({`K POT.1, K POT.2, 1 POT.2}) - which is the Erdos and Hajnal [5] class ofsimplegraphs - then r ind(G,H) < `[V(H)]POT.f¦, where f is constant that only depends on G
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2022-07-13
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2024. All rights reserved.