25 de fevereiro de 2026
Sala de Seminários do Bloco 952, Campus do Pici, Fortaleza
Como chegar: https://maps.app.goo.gl/ZnUNkytfkY7uJxYJ7
Programação:
10:00 - Taísa Martins (UFF)
Título: "Uma versão multicolorida da conjectura de Lehel"
Resumo: "A conjectura de Lehel estabelece que toda 2-coloração das arestas de um grafo completo com n vértices permite particionar o conjunto de vértices em dois ciclos monocromáticos. Esse problema foi resolvido para n suficientemente grande por Łuczak, Rödl e Szemerédi (1998), posteriormente estendido por Allen (2008) e definitivamente solucionado por Bessy e Thomassé (2010). Nesta palestra, apresentamos uma generalização multicolorida dessa conjectura no contexto de grafos completos com coloração própria das arestas. Mostramos que, para n suficientemente grande, qualquer coloração própria das arestas de um grafo completo admite uma partição dos vértices em dois ciclos multicoloridos (ou arco-íris), isto é, ciclos em que todas as arestas têm cores distintas.
Este é um trabalho em conjunto com Pedro Araújo, Xiao-Chuan Liu, Walner Mendonça, Luiz Moreira, Vinicius Fernandes dos Santos e Zhifei Yan."
11:00 - Vinícius Fernandes dos Santos (UFMG)
Título: "Exploring subgraph complementation to bounded degree graphs"
Resumo: "Graph modification problems are computational tasks where the goal is to change an input graph G using operations from a fixed set, in order to make the resulting graph satisfy a target property, which usually entails membership to a desired graph class C. Some well-known examples of operations include vertex-deletion, edge-deletion, edge-addition and edge-contraction. In this paper we address an operation known as subgraph complement. Given a graph G and a subset S of its vertices, the subgraph complement G⊕S is the graph resulting of complementing the edge set of the subgraph induced by S in G. We say that a graph H is a subgraph complement of G if there is an S such that H is isomorphic to G⊕S. For a graph class C, subgraph complementation to C is the problem of deciding, for a given graph G, whether G has a subgraph complement in C. This problem has been studied and its complexity has been settled for many classes C such as H-free graphs, for various families H, and for classes of bounded degeneracy. In this work, we focus on classes graphs of minimum/maximum degree upper/lower bounded by some value k. In particular, we answer an open question of Antony et al. [Information Processing Letters 188, 106530 (2025)], by showing that subgraph complementation to C is NP-complete when C is the class of graphs of minimum degree at least k, if k is part of the input. We also show that subgraph complementation to k-regular parameterized by k is fixed-parameter tractable." Joint work with Nina Pardal and Ivo Koch.
14:00 - Sheila Almeida (UTFPR)
Título: "Colorações distinguidoras de vértices: técnicas, resultados e desafios"
Resumo: "Nesta palestra serão abordados problemas de coloração distinguidora de vértices. Inicialmente, serão apresentados os conceitos de coloração de arestas própria e coloração total própria, bem como os problemas clássicos de coloração correspondentes. Na sequência, serão definidas as noções de coloração de arestas distinguidora de vértices e coloração de arestas distinguidora de vértices adjacentes, assim como coloração total distinguidora de vértices e coloração total distinguidora de vértices adjacentes. Nessas colorações próprias, cada vértice é rotulado pelo conjunto das cores das arestas nele incidentes e, no caso da coloração total, também por sua própria cor, exigindo-se que os rótulos de quaisquer dois vértices (ou, na versão adjacente, de quaisquer dois vértices adjacentes) sejam distintos. O Problema da Coloração Total Distinguidora de Vértices (Adjacentes) consiste em minimizar o número de cores necessárias para se obter tal coloração em um dado grafo. Serão discutidas as principais abordagens que têm sido adotadas pelo grupo da UTFPR para esses problemas em classes específicas de grafos, com ênfase em grafos de indiferença, particularmente em potências de caminhos, e em grafos k-partidos completos com k limitado a 5. Tais resultados são fruto de uma linha de pesquisa ativa desde 2016, envolvendo dissertações de mestrado e trabalhos de conclusão de curso. Serão apresentadas as principais técnicas adotadas, resultados conhecidos e obtidos recentemente, e alguns desafios."
15:00 - Guilherme Mota (USP)
Título: "Limiares para Propriedades de Ramsey em Grafos Aleatórios"
Resumo: "Esta apresentação aborda funções limiares para propriedades do tipo Ramsey no contexto de grafos aleatórios. Introduziremos a notação $G \to (K_r, K_s, K_t)$, que indica que qualquer coloração das arestas de $G$ contém necessariamente uma cópia monocromática de $K_r$, uma cópia multicolorida (rainbow) de $K_s$ ou uma cópia lexicográfica de $K_t$. Além de revisar resultados clássicos da área, discutiremos avanços recentes e novos limites para a função limiar dessa propriedade, analisando diferentes configurações dos parâmetros $r, s$ e $t$."
16:00 - Júlio Araújo (UFC)
Título: "Maya-Tupi graphs: a generalization of split graphs"
Resumo: "We define the family of Maya-Tupi graphs as those graphs that admit a partition (A,B) of their vertex sets such that A induces a complete multipartite graph where each part has size at most two, and B induces a graph where every connected component is K1 or K2. The family of Maya-Tupi graphs is self complementary, generalizes split graphs, falls into the sparse-dense partitioning schema and is characterized by finitely many forbidden induced subgraphs. Unfortunately, our computational experiments show that the number of minimal forbidden induced subgraphs to characterize Maya-Tupi graphs is greater than 2000. In this work, we study Maya-Tupi graphs when restricted to some well-known graph classes. We find characterizations in terms of minimal forbidden induced subgraphs for disconnected graphs, trees and cographs; our results imply linear time certifying recognition algorithms for Maya-Tupi graphs within these classes. We also show that Maya-Tupi graphs can be recognized in O(n^3)-time in C4-free graphs and in graphs with bounded neighborhood diversity."
This is a joint work with César Hernández-Cruz (UNAM, México) and Cláudia Linhares (UFC, Brasil).