2-Reachable Subsets in Two-Colored Graphs

Abstract 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mfrac> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:mfrac> </mml:math> vertices (and this is best possible).