Ramsey-type problems in orientations of graphs - Cavalar, Bruno Pasqualotto (Anais do Encontro de Teoria da Computação (ETC), 2018)
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 ∈ V (H → ) and their respective copies x', y' in G → , the distance between x and y is equal to the distance between x' and y'.