---

Statement

Notation as on the Theorem 1 page.

Definition (p. 295, quoted). "A graph $G'$ is a vertex-critical Ramsey graph for $G$ iff $G\xrightarrow[2]{}G'$, and $G\not\xrightarrow[2]{}G''$ for every vertex deleted subgraph $G''$ of $G$ [sic]." The final "of $G$" is as printed; the sense requires "of $G'$". Every critical Ramsey graph for $G$ is vertex-critical (p. 295).

Conjecture 1 (p. 295, quoted). "For a graph $G$, the following three statemens [sic] are equivalent:

1. $G$ has an infinite number of nonisomorphic vertex-critical Ramsey graphs
2. $G\not\xrightarrow[2]{}G$
3. $G$ contains at least two edges."

The conjecture is attributed to the authors' earlier paper, Partitions of vertices, Comment. Math. Univ. Carolinae 17 (1976), 85--95 (the paper's [6]). The paper calls 1)$\Rightarrow$2), 1)$\Rightarrow$3) and 2)$\Leftrightarrow$3) obvious, so the open part is 3)$\Rightarrow$1). It proves that implication for the graphs covered by Theorem 1, Theorem 2 and the forest theorem, in the stronger form for critical Ramsey graphs, and says it did not reach the full solution (p. 296). For critical rather than vertex-critical Ramsey graphs the analogue fails: a graph with $G\not\xrightarrow[2]{}G$ can have only finitely many critical Ramsey graphs, for example $k$ disjoint edges or a star with an odd number of edges, citing Burr, Erdős and Lovász (p. 295). For partitions of vertices instead of edges, the paper states that the analogue of Conjecture 1 is true, by the methods of [6] (p. 299).

Source. J. Nešetřil and V. Rödl, The structure of critical Ramsey graphs, Acta Math. Acad. Sci. Hungar. 32 (1978), no. 3--4, 295--300, doi:10.1007/BF01902367; the definition and Conjecture 1 on p. 295, remark 3) on p. 299. Edition as on the source card.

Read depth. Claims checked: read clause by clause on the page images. Nothing here is independently reviewed.

Bears on

No problem page consumes this conjecture.