Document Type : Research Paper

Authors

• Kristiana Wijaya ¹
• Lyra Yulianti ²
• Edy Tri Baskoro ³
• Hilda Assiyatun ³
• Djoko Suprijanto ³

¹ Combinatorial Mathematics Research Group, Faculty of Mathematics and natural Sciences, Institut Teknologi Bandung (ITB), Jalan Ganesa 10 Bandung 40132 Indonesia

² Department of Mathematics, Faculty of Mathematics and Natural Sciences, Andalas University, Kampus UNAND Limau Manis Padang 25136 Indonesia

³ Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung (ITB), Jalan Ganesa 10 Bandung 40132 Indonesia

Abstract

Let F, G and H be non-empty graphs. The notation F → (G,H) means that if any edge of F is colored by red or blue, then either the red subgraph of F con- tains a graph G or the blue subgraph of F contains a graph H. A graph F (without isolated vertices) is called a Ramsey (G,H)−minimal if F → (G,H) and for every e ∈ E(F), (F − e) 9 (G,H). The set of all Ramsey (G,H)−minimal graphs is denoted by R(G,H). In this paper, we characterize all graphs which are in R(2K2,C4).

Keywords

• Ramsey minimal graph
• edge coloring
• graph 2K2
• cycle graph