PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-isomorphic graphs have distinct vertex-Ramsey classes

Maria Axenovich, Patrick Schmitteckert

arXiv:2610.03704v1math.COcs.ITmath.IT

TL;DR

The paper addresses whether non-isomorphic graphs can have the same vertex Ramsey class, against the backdrop of an analogous edge-colouring question that remains open in general. It constructs separating Ramsey graphs and proves that the classes are distinct for every positive number of colours.

  • Problem

    Whether non-isomorphic graphs have distinct Ramsey classes has been asked for edge colourings, with the general question still open; the paper addresses the analogous vertex-colouring question.

    Source: §1 · p. 1

  • Method

    The proof constructs graphs that belong to one graph’s vertex Ramsey class but not the other’s, using cases based on graph order and constructions involving induced copies.

    Source: §3 · p. 2, §2 · p. 2

  • Results

    For every positive integer k, any two non-isomorphic graphs have distinct k-colour vertex Ramsey classes.

    Source: §1 · p. 1

  • Takeaways & Limitations

    Vertex Ramsey classes distinguish non-isomorphic graphs, including graphs that are not connected.

    Source: §1 · p. 1

    The proof’s final case assumes the two graphs are non-isomorphic, connected, and each contains at least one edge.

    Source: §3 · p. 3

Abstract

from arXiv · show

For a graph $H$, its $k$-colour vertex Ramsey class is the set of all graphs $G$ such that any colouring of the vertices of $G$ in $k$ colours results in a monochromatic (induced) copy of $H$. We prove that for any $k$, Ramsey classes of any non-isomorphic graphs are distinct.

1 Introduction

The introduction defines vertex Ramsey classes and states that any two non-isomorphic graphs have distinct classes for every positive number of colours. This answers the analogous question for vertex colourings, while the cited edge-colouring question remains open in general.

  • A k-colour vertex Ramsey class contains graphs where every k-colouring has a monochromatic copy of H; the induced version requires that copy to be induced.Source: §1 · p. 1
  • Folkman first showed that the induced k-colour vertex Ramsey class of every graph is nonempty.The introduction also points to for vertex Ramsey theory results.Source: §1 · p. 1
  • For every positive integer k, non-isomorphic graphs have distinct k-colour vertex Ramsey classes.Source: §1 · p. 1
  • The result answers positively the analogous question for vertex colourings and all graphs, whereas the corresponding edge-colouring question remains open in general.Source: §1 · p. 1

2 Notation and Ramsey properties

This section introduces graph notation and Ramsey repetition, characterizes repetition by connectedness, and gives a hypergraph-based construction of induced vertex-Ramsey graphs.

2 Notation and Ramsey properties

  • The notation defines order, size, complement, independence number, block order β(H), graph join, and Forb(H) for graphs with no induced H.For edgeless H, β(H)=1; otherwise it is the largest order of a block.Source: §2 · p. 1
  • Construction 1 forms a graph from copies of H placed on hyperedges, yielding a graph in the induced k-colour vertex Ramsey class of H.The hypergraph is |H|-uniform, has girth at least q, and chromatic number at least k+1; the girth condition ensures the monochromatic copy is induced.Source: §2 · pp. 1–2
  • A graph has the Ramsey repetition property exactly when it is connected.The property means that q disjoint copies of any graph A belong to Rk(H) for every q≥1.Source: §2 · p. 2
  • Connected graphs have the Ramsey repetition property, while disconnected graphs do not.Source: §2 · p. 2

3 Proof of Theorem 1.1

The proof separates the Ramsey classes of non-isomorphic graphs by constructing distinguishing witnesses, handling graph-order cases directly and the induced-class case recursively. The recursive construction combines a graph avoiding H1 with attached copies that force a monochromatic induced H2.

Direct cases

  • For k=1, each graph belongs to its own Ramsey class, so non-isomorphic graphs have distinct classes.Source: §3 · p. 2
  • For unequal orders, K_(k(n−1)+1) is Ramsey for the smaller graph but admits a k-colouring with no monochromatic copy of the larger graph.Here n is the order of the smaller graph.Source: §3 · p. 2
  • For equal orders, choosing H1 not to be a subgraph of H2 gives a graph Ramsey for H2 but colourable without a monochromatic H1.The witness is H2∨K_(k−1)(n−1); colour H2 red and distribute the remaining vertices among the other k−1 colours.Source: §3 · p. 2

Induced Ramsey classes

  • For the induced-class proof, the graphs can be taken connected with edges, and an independent set I in H2 gives F=H2−I with β(F)<β(H2)≤β(H1).The proof describes selecting I block by block in the block-cutvertex tree.Source: §3 · pp. 2–3
  • Construction 1 provides A avoiding H1 and belonging to Rk_ind(F), using a block B of H1 and a hypergraph with girth at least ||B||+2.If F is edgeless, the proof instead takes an edgeless graph on k(|F|−1)+1 vertices.Source: §3 · p. 3
  • Starting with A1=H2, each Ar is built by attaching disjoint copies of Ar−1 to induced copies of F according to H2-neighbourhoods.The attached copies are pairwise vertex-disjoint from one another and from A.Source: §3 · p. 3
  • The recursive construction yields a graph avoiding H1 while forcing a monochromatic induced H2 in every r-colouring.The proof distinguishes whether an attached copy uses at most r−1 colours or all r colours; in the latter case, selected red vertices combine with a red copy of F.Source: §3 · pp. 3–4
Loading 2610.03704v1…