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)
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)
15:00 - Guilherme Mota (USP)
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).