.png){kind=icon}
.png){kind=icon}
Return
2-Reachable Subsets in Two-Colored Graphs
.png){kind=icon}
PRE
AI
DOI：10.1007/s00373-026-03036-6.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 n2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n\over 2$$\end{document} vertices (and this is best possible).
Keywords:
Diameter in Ryser's conjecture
2-coloring cocktail party graphs
Journal
G
IF:
0.6
Papers:
80
Citations:
0