Ramsey Goodness of paths versus K3,t - Botler, Fábio; Moreira, Luiz Paulo Freire; Souza, João Pedro de (Anais do Encontro de Teoria da Computação (ETC); 2025: Anais do X Encontro de Teoria da Computação, 2025)
Dado grafos G e H, dizemos que G é H-good se o número de Ramsey R(G,H) for igual ao limitante inferior trivial (|G| − 1)(χ(H) − 1) + σ(H), onde χ(H) denota o número cromático usual de H, e σ(H) denota o tamanho mínimo de uma classe de cor em uma χ(H)-coloração de H. Em 2013, Allen et al. conjecturaram que P n é H-good para todo n ≥ χ(H)|H|. Um resultado de Pokrovskiy e Sudakov (2017) implica que tal conjectura vale quando χ(H) ≥ 4. Nós estudamos o caso χ(H) = 2 e provamos que P n é H-good para todo n ≥ 2 · |V(H)|, com H ⊆ K 3,t .