2-Reachable Subsets in Two-Colored Graphs
Graphs and Combinatorics · 2026-04 · 42 (2)
DOI: 10.1007/s00373-026-03036-6 ↗Kurz gefasst
Fachartikel in der Zeitschrift Graphs and Combinatorics, online erschienen am 25.03.2026. Verfasst von András Gyárfás und 1 weiteren Autor:innen. Die Arbeit nennt 14 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: HUN-REN Alfréd Rényi Institute of Mathematics.
Abstract (Originalsprache)
A subset X of vertices in a graph G is a diameter 2 subset if the distance of any two vertices of X is at most two in G[X] . Relaxing this notion, a subset X of vertices in a graph G is a 2-reachable subset if the distance of any two vertices of X is at most two in G . Related to recent attempts to strengthen a well-known conjecture of Ryser, English et al. conjectured that the vertices of a 2-edge-colored cocktail party graph (the graph obtained from a complete graph with an even number of vertices by deleting a perfect matching) can be covered by the vertices of two monochromatic diameter 2 subsets. In this note we prove the relaxed form of this conjecture, replacing diameter 2 by 2-reachable. An immediate corollary is that 2-colored cocktail party graphs on n vertices must contain a monochromatic 2-reachable subset with at least $$n\over 2$$ n 2 vertices (and this is best possible).
Förderung
- HUN-REN Alfréd Rényi Institute of Mathematics
Zitieren
APA
Gyárfás, A., & Sárközy, G. N. (2026). 2-Reachable Subsets in Two-Colored Graphs. Graphs and Combinatorics, 42(2). https://doi.org/10.1007/s00373-026-03036-6
Vancouver
Gyárfás A, Sárközy GN. 2-Reachable Subsets in Two-Colored Graphs. Graphs and Combinatorics. 2026;42(2). doi:10.1007/s00373-026-03036-6
BibTeX
@article{Gyrfs2026,
author = {Gyárfás, András and Sárközy, Gábor N.},
title = {2-Reachable Subsets in Two-Colored Graphs},
journal = {Graphs and Combinatorics},
year = {2026},
volume = {42},
number = {2},
doi = {10.1007/s00373-026-03036-6}
}
EUVIMED