All Ramsey (C_n,K₆) critical graphs for large n

Publication date: 5 February 2019

Abstract: Let

G

and

H

be finite graphs. If for any two-coloring of the edges of a complete graph

K_{n}

, there is a copy of

G

in the first color, red, or a copy of

H

in the second color, blue, we will say

K_{n} i g h t a r r o w (G, H)

. The Ramsey number

r (G, H)

is defined as the smallest positive integer

n

such that

K_{n} i g h t a r r o w (G, H)

. A two-coloring of

K_{r (G, H) - 1}

such that

K_{r (G, H) - 1} o t i g h t a r r o w (G, H)

is called a critical coloring. A Ramsey critical

r (G, H)

graph is a graph induced by the first color of a critical coloring. In this paper, when

n g e q 15

, we show that there exist exactly sixty eight non-isomorphic Ramsey critical

r (C_{n}, K_{6})

graphs.

This page was built for publication: All Ramsey $(C_n,K_6)$ critical graphs for large $n$