TOPICS
Search

Vertex Ramsey Class


The k-color vertex Ramsey class R^k(H) of a finite nonempty graph H is the class of graphs G for which every vertex coloring with k colors contains a subgraph isomorphic to H whose vertices all have the same color. These colorings need not be proper. The induced vertex Ramsey class R_(ind)^k(H) instead requires a vertex-induced subgraph of this kind.

Axenovich and Schmitteckert (2026) proved that for any two nonisomorphic finite nonempty graphs H_1,H_2 and every positive integer k,

 R^k(H_1)!=R^k(H_2),

and likewise

 R_(ind)^k(H_1)!=R_(ind)^k(H_2).

Thus either type of vertex Ramsey class determines its defining graph up to graph isomorphism.


See also

Graph Isomorphism, Ramsey Theory, Vertex Coloring, Vertex-Induced Subgraph

Explore with Wolfram|Alpha

References

Axenovich, M. and Schmitteckert, P. "Non-Isomorphic Graphs Have Distinct Vertex-Ramsey Classes." 2 Oct 2026. https://arxiv.org/abs/2610.03704.

Cite this as:

Weisstein, Eric W. "Vertex Ramsey Class." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/VertexRamseyClass.html

Subject classifications