Zixia Song

University of Central Florida

Abstract

Given an integer r ≥ 1 and graphs G, H₁, . . . , H_r, we write G → (H₁, . . . , H_r) if every r-coloring of the edges of G contains a monochromatic copy of H_i in color i for some i ∈ {1, . . . , r}. A non-complete graph G is (H₁, . . . , H_r)-co-critical if G ↛ (H₁, . . . , H_r), but G + e → (H₁, . . . , H_r) for every edge e in the complement of G. Motivated by Hanson and Toft’s conjecture, we study the minimum number of edges over all (H₁, . . . , H_r)-co-critical graphs on n vertices. In this talk we will survey the history of (H₁, . . . , H_r)-co-critical graphs and discuss the main ideas of our recent results on co-critical graphs.