Recent algorithmic results on equitable coloring

Speaker: Vinicius Santos, UFMG.

Date: 18 dec 2019, 11h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: A proper coloring of a graph is a labeling of its vertex set such that adjacent vertices receive distinct labels. Many problems can be modelled using graph colorings, such as scheduling and task assignment problems. On such problems, one may be interested in the case where the coloring is balanced in the following sense: the number of times two different colors occurs in the graph can differ by at most one. Such proper colorings are called equitable colorings.

Similarly to the traditional version, determining whether a graph has an equitable coloring with a given amount of colors is a computationally hard problem. However, for many settings where coloring is tractable, the problem becomes hard for the equitable version. In this talk we present some recent advances on this problem, such as polynomial time algorithms for some special cases and positive and negative results concerning the parameterized complexity of the problem.

This is joint work with Matheus Guedes and Guilherme Gomes.

 

Introdução sobre complexidade parametrizada e problemas

Speakers: Ignasi Sau, LIRMM; Ueverton Souza, IC-UFF.

Date: 27 nov 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: Nesta palestra faremos uma breve introdução sobre algoritmos e complexidade parametrizada, uma das áreas mais promissoras da teoria da computação. Em seguida serão apresentados alguns problemas de nosso interesse particular tais como deleção de vértices em grafos com bounded treewidth para obtenção de estruturas livres de certos subgrafos induzidos. Em especial abordaremos o desenvolvimento de algoritmos de tempo single-exponencial com relação a treewidth do grafo de entrada para resolução problemas como deleção de vértices para obtenção de grafos livres de conjuntos independentes induzidos de tamanho k.

 

Jogo Mapa do Tesouro

Speaker: Andressa Martins Moraes, UFRJ/PPGI/AMN.

Date: 30 sep 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: Neste seminário apresentarei o Jogo Mapa do Tesouro, um jogo em grafos aplicado na educação com objetivo de avaliar o desenvolvimento da aprendizagem utilizando conceitos da neurociência e empregando uma estrutura baseada em grafos.

 

The size-Ramsey number of powers of bounded degree trees

Speaker: Taísa Martins, IMPA.

Date: 28 aug 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: Given a positive integer s, the s-colour size-Ramsey number of a graph H is the smallest integer m such that there exists a graph G with m edges where in any s-colouring of E(G) there is a monochromatic copy of H. We prove that, for any positive integers k and s, the s-colour size-Ramsey number of the kth power of any n-vertex tree is linear on n.

This is a joint work with S. Berger, Y. Kohayakawa, G. S. Maesaka, W. Mendonça, G. O. Mota and O. Parczyk.

 

Dificuldade e Eficiência de Problemas em Grafos, Strings e Permutações

Speaker: Luis Felipe Ignácio Cunha, IME-UFF.

Date: 21 aug 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: Neste seminário, trataremos de problemas em grafos, strings e permutações. Estes problemas são desafiadores do ponto de vista combinatório e possuem muitas questões intrigantes há anos. Apresentaremos nosso avanços nos estudos abaixo.

-- Admissibilidade: desejamos obter num grafo G o menor inteiro t, tal que exista uma árvore geradora T cuja distância em T entre cada par de vértices vizinhos de G seja no máximo t;
-- Tesselabilidade: uma tesselação de um grafo G é uma partição do conjunto de vértices em cliques. Desejamos obter o menor t, tal que existam t tesselações cuja união das tesselações cubra o conjunto das arestas do grafo;
-- Blocos haplótipos: dadas k strings binárias, desejamos obter todas subsequências maximais cujos elementos em cada coluna sejam iguais.
-- Indexação de strings: desejamos preprocessar uma string binária de modo a responder em tempo constante se há uma substring de tamanho k com i cópias de 1s, para valores arbitrários de k e i;
-- Distância, Diâmetro, Centralidade, Mediana e Convexidade em permutações: estes são problemas associados a grupos simétricos de permutações, que possuem muitas aplicações em biologia matemática, cujo intuito é compreender melhor a filogenia de espécies.
Além de estudos obtidos nesses temas, serão apresentadas as colaborações em pesquisa e atividades de ensino e extensão em desenvolvimento.

 

Sobre coloração total equilibrada de grafos multipartidos completos balanceados

Speaker: Anderson G. da Silva, Universidade de Delaware.

Date: 26 jun 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: Uma coloração total é a aplicação de cores aos vértices e arestas de um grafo de modo que elementos adjacentes ou incidentes recebam cores distintas. O número cromático total de um grafo é o menor inteiro positivo para o qual o grafo possui coloração total. Dada uma coloração total, se a diferença entre as cardinalidades de quaisquer duas classes de cor for no máximo um, então dizemos que a coloração é equilibrada e o menor número inteiro positivo que satisfaz essa condição é dito o número cromático total equilibrado do grafo. Para tal valor, Wang (2002) conjecturou um limite superior. Um grafo multipartido completo balanceado é aquele em que o conjunto de vértices pode ser particionado em conjuntos independentes com a mesma quantidade de vértices, sendo adjacentes quaisquer dois vértices de diferentes partes da partição. Determinamos o número cromático total equilibrado dos grafos multipartidos completos balanceados, contribuindo, desta forma, com novos resultados na área de coloração de grafos.

Trabalho em conjunto com Diana Sasaki (UERJ) e Simone Dantas (UFF).

 

A general method for forbidden induced subgraph sandwich problem NP-completeness

Speaker: Rafael Bernardo Teixeira, ICE-UFRRJ.

Date: 29 apr 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: We consider the sandwich problem, a generalization of the recognition problem introduced by Golumbic and Shamir (1993), with respect to classes of graphs defined by excluding induced subgraphs. The Π graph sandwich problem asks, for a pair of graphs G1 = (V, E1) and G2 = (V, E2) with E1 ⊆ E2, whether there exists a graph G = (V, E) with E1 ⊆ E ⊆ E2 that satisfies property Π. We consider the property of being H-free, where H is a fixed graph. Using a new variant of the SAT problem, we present a general framework to establish the NP-completeness of the sandwich problem for several H-free graph classes which generalizes the previous strategy for the class of Hereditary clique-Helly graphs. We also provide infinite families of 3-connected special forbidden induced subgraphs for which each forbidden induced subgraph sandwich problem is NP-complete.

Obs.: Joint work with Simone Dantas (UFF), Celina M. H. de Figueiredo (COPPE-UFRJ) and Priscila Petito (UERJ).

 

Controlabilidade de Fronteira Livre para Equação do Calor 1D com Não-linearidades Locais e Não-locais

Speaker: Vitor Costa, IME-UERJ.

Date: 27 mar 2019, 14h.

Place: Room 411, Bloco H, Campus Gragoatá, UFF.

Abstract: Neste trabalho apresentamos o problema de controle com fronteira livre para equações do calor não-lineares 1D com um controle local atuando na variável espacial. O principal resultado mostra que, se o dado inicial é suficientemente pequeno, então a solução do sistema é conduzida a zero no tempo t=T.

 

Women in Science

Speaker: Luise-Charlotte Kappe, Binghamton University.

Date: 27 feb 2019.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

11:30h: Finite coverings: a journey through groups, loops, rings, and semigroups.

14h: It's a wonderful life! - Reflections on a career as a mathematician.

Mulheres na Ciência 2