2-reachable subsets in two-colored graphs
2-reachable subsets in two-colored graphs
A subset $X$ of vertices in a graph $G$ is a {\em diameter 2 subset} if the distance of any two vertices of $X$ is at most two {\em in $G[X]$}. Relaxing this notion, a subset $X$ of vertices in a graph $G$ is a {\em 2-reachable subset} if the distance of any two vertices of $X$ is at most two {\em 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$ vertices (and this is best possible).
Andras Gyarfas、Gabor N. Sarkozy
数学
Andras Gyarfas,Gabor N. Sarkozy.2-reachable subsets in two-colored graphs[EB/OL].(2025-06-13)[2025-06-27].https://arxiv.org/abs/2506.11696.点此复制
评论