TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publication References
  4. Ramsey equivalence for asymmetric pairs of graphs
 
Options

Ramsey equivalence for asymmetric pairs of graphs

Publikationstyp
Journal Article
Date Issued
2024
Sprache
English
Author(s)
Boyadzhiyska, Simona  
Clemens, Dennis  orcid-logo
Mathematik E-10  
Gupta, Pranshu  
Mathematik E-10  
Rollin, Jonathan  
FernUniversität in Hagen
TORE-URI
https://hdl.handle.net/11420/46088
Journal
SIAM journal on discrete mathematics  
Volume
38
Issue
1
Start Page
55
End Page
74
Citation
SIAM Journal on Discrete Mathematics 38 (1): 55-74 (2024)
Publisher DOI
10.1137/23M1558239
Scopus ID
2-s2.0-85184840739
Publisher
SIAM
A graph F is Ramsey for a pair of graphs (G, H) if any red/blue-coloring of the edges of F yields a copy of G with all edges colored red or a copy of H with all edges colored blue. Two pairs of graphs are called Ramsey equivalent if they have the same collection of Ramsey graphs. The symmetric setting, that is, the case G = H, received considerable attention. This led to the open question whether there are connected graphs G and G\prime such that (G, G) and (G\prime, G\prime) are Ramsey equivalent. We make progress on the asymmetric version of this question and identify several nontrivial families of Ramsey equivalent pairs of connected graphs. Certain pairs of stars provide a first, albeit trivial, example of Ramsey equivalent pairs of connected graphs. Our first result characterizes all Ramsey equivalent pairs of stars. The rest of the paper focuses on pairs of the form (T, Kt), where T is a tree and Kt is a complete graph. We show that if T belongs to a certain family of trees, including all nontrivial stars, then (T, Kt) is Ramsey equivalent to a family of pairs of the form (T, H), where H is obtained from Kt by attaching disjoint smaller cliques to some of its vertices. In addition, we establish that for (T, H) to be Ramsey equivalent to (T, Kt), H must have roughly this form. On the other hand, we prove that for many other trees T, including all odd-diameter trees, (T, Kt) is not equivalent to any such pair, not even to the pair (T, Kt \cdot K2), where Kt \cdot K2 is a complete graph Kt with a single edge attached.
Subjects
graph Ramsey theory
Ramsey equivalence
DDC Class
510: Mathematics
TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback