Ramsey-type problems in orientations of graphs ⇤

  • Bruno Pasqualotto Cavalar

Resumo


The Ramsey number R(H) of a graph H is the minimum number n such that there exists a graph G on n vertices with the property that every two-coloring of its edges contains a monochromatic copy of H. In this work we study a variant of this notion, called the oriented Ramsey problem, for an acyclic oriented graph H~ , in which we require that every orientation G~ of the graph G contains a copy of H~ . We also study the threshold function for this problem in random graphs. Finally, we consider the isometric case, in which we require the copy to be isometric, by which we mean that, for every two vertices x, y 2 V (H~ ) and their respective copies x0, y0 in G~ , the distance between x and y is equal to the distance between x0 and y0.

Publicado
26/07/2018
CAVALAR, Bruno Pasqualotto. Ramsey-type problems in orientations of graphs ⇤. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3172.