Star-Critical Ramsey Numbers (2009)

Originator: Garth Isaak    (presented by Garth Isaak - REGS 2010)

Definitions: In an edge-colored graph, a monochromatic subgraph is a subgraph whose edges all have the same color. The graph Ramsey number R(G,H) is the least r such that every red/blue-coloring of the edges of the complete graph Kr contains either a red copy of G or a blue copy of H. The critical colorings when R(G,H)=r are the red/blue-colorings of Kr-1 having no such subgraph.

Let Kn[k] denote the n-vertex graph obtained from Kn-1 by adding one new vertex adjacent to k of the earlier vertices (thus Kn=Kn[n-1]). The star-critical Ramsey number r*(G,H) is the least k such that every red/blue-coloring of the edges of KR(G,H)[k] contains a red copy of G or a blue copy of H.

Background: The star-critical Ramsey numbers are motivated by the following (incorrect) inductive proof idea for graph Ramsey numbers: start with a critical edge-coloring of KR(G,H)-1 and show that adding and coloring the edges to an additional vertex forces a red G or a blue H. The star-critical Ramsey number is the least k such that no critical coloring can be extended by k edges to a new vertex and still avoid the specified monochromatic subgraphs. This parameter combines the notions of Ramsey number and size Ramsey number, where the size Ramsey number for the pair (G,H) is the minimum number of edges in a graph F whose red/blue-edge-colorings all contain a red G or a blue H.

Problem 1: For given pairs (or classes of pairs) (G,H), determine the critical colorings and the star-critical Ramsey number.

Comments: This problem is quite wide open, with much work to be done and answers for many small instances still unknown. The difficulty is that critical edge-colorings for pairs (G,H) generally have not been determined, even when R(G,H) is known. In particular, many known graph Ramsey numbers are listed in the survey [Rad], but for most of them the critical colorings seem not to have been determined.

Classification of critical graphs and determination of star-critical Ramsey numbers for some pairs and classes of pairs appear in Hook [H] and in Hook & Isaak [HI]. We describe several examples.

  • R(K1,s,K1,t)=s+t when s and t are both odd, and the critical colorings are those in which the red graph is (s-1)-regular and the blue graph is (t-1)-regular. Adding just one edge forces a vertex with sufficient degree in one of the colors, so the star-critical Ramsey number is 1.
  • The Ramsey number for two complete graphs is not known, but it is known that the star-critical Ramsey number is one less than it. Duplicating one vertex in a critical edge-coloring adds R(Ks,Kt) edges but does not force the monochromatic subgraph.
  • R(Pn,P3)=n for n≥3, and the star-critical Ramsey number is 2. The more general case where G and H are both paths of any length has also been solved.
  • R(T,Kn)=m(n-1)+1 for any tree T with m edges. There is a unique critical edge-coloring, in which the red graph is (n-1)Km. When extending the critical edge-coloring to a new vertex, one cannot add any red edge, and one cannot add a blue edge joining the new vertex to each component of the old graph, so the star-critical Ramsey number is n-1.
  • R(Pn,Cm)=2n-1 when m is odd and n≥m. There are four types of critical colorings, and the star-critical Ramsey number has been determined. (What is it?)
  • The problem has also been solved when G and H are both matchings, when both are disjoint unions of triangles, when G is a cycle and H is a complete graph with at most four vertices, and for a few other special cases.

    • Finally, one can pursue generalizations analogous to ordinary graph Ramsey theory, asking the corresponding questions when more colors are allowed or when the forbidden monochromatic structure is any graph in some family of graphs.

    References: [H] Hook, Jonelle, Star-Critical Ramsey Numbers; PhD Thesis Lehigh University May 2010
    [HI] Hook, Jonelle and Isaak, Garth, Star-Critical Ramsey Numbers, manuscript, submitted November 2009.
    [Rad] Radziszowski, Stanislaw, Small Ramsey Numbers, Electronic Journal of Combinatorics, Dynamic survey DS1.