On characterizing the critical graphs for matching Ramsey numbers

Abstract: Given simple graphs

H_{1}, H_{2}, l d o t s, H_{c}

, the Ramsey number

r (H_{1}, H_{2}, l d o t s, H_{c})

is the smallest positive integer

n

such that every edge-colored

K_{n}

with

c

colors contains a subgraph in color

i

isomorphic to

H_{i}

for some

i i n 1, 2, l d o t s, c

. The critical graphs for

r (H_{1}, H_{2}, l d o t s, H_{c})

are edge-colored complete graphs on

r (H_{1}, H_{2}, l d o t s, H_{c}) - 1

vertices with

c

colors which contain no subgraphs in color

i

isomorphic to

H_{i}

for any

i i n 1, 2, l d o t s, c

. For

n_{1} g e q n_{2} g e q l d o t s g e q n_{c} g e q 1

, Cockayne and Lorimer (The Ramsey number for stripes, {it J. Austral. Math. Soc.} extbf{19} (1975), 252--256.) showed that

r (n_{1} K_{2}, n_{2} K_{2}, l d o t s, n_{c} K_{2}) = n_{1} + 1 + s u m l i m i t s_{i = 1}^{c} (n_{i} - 1)

, in which

n_{i} K_{2}

is a matching of size

n_{i}

. Using the Gallai-Edmonds Theorem, we characterized all the critical graphs for

r (n_{1} K_{2}, n_{2} K_{2}, l d o t s, n_{c} K_{2})

, implying a new proof for this Ramsey number.

Recommendations

Cites Work

Cited In (2)

This page was built for publication: On characterizing the critical graphs for matching Ramsey numbers