Veröffentlichung

Titel:

Conditions on Ramsey non-equivalence

AutorInnen:

Maria Axenovich
Jonathan Rollin
Torsten Ueckerdt

Kategorie:

Artikel in Zeitschriften

erschienen in:

Journal of Graph Theory, Vol. 86, No. 2, pp. 159–192, 2017

Abstract:

Given a graph H, a graph G is called a Ramsey graph of H if there is a monochromatic copy of H in every coloring of the edges of G with two colors. Two graphs G, H are called Ramsey equivalent if they have the same set of Ramsey graphs. Fox et al. (J Combin Theory Ser B 109 (2014), 120–133) asked whether there are two nonisomorphic connected graphs that are Ramsey equivalent. They proved that a clique is not Ramsey equivalent to any other connected graph. Results of Nešetřil et al. showed that any two graphs with different clique number (Combinatorica 1(2) (1981), 199–202) or different odd girth (Comment Math Univ Carolin 20(3) (1979), 565–582) are not Ramsey equivalent. These are the only structural graph parameters we know that “distinguish” two graphs in the above sense. This article provides further supportive evidence for a negative answer to the question of Fox et al. by claiming that for wide classes of graphs, the chromatic number is a distinguishing parameter. In addition, it is shown here that all stars and paths and all connected graphs on at most five vertices are not Ramsey equivalent to any other connected graph. Moreover, two connected graphs are not Ramsey equivalent if they belong to a special class of trees or to classes of graphs with clique‐reduction properties.

Download:

arXiv

BibTeX-Eintrag:

@article{, author = {Maria Axenovich and Jonathan Rollin and Torsten Ueckerdt}, title = {Conditions on Ramsey Nonequivalence}, journal = {Journal of Graph Theory}, volume = {86}, number = {2}, pages = {159--192}, year = {2017}, }