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

 

Pagina 2 de 2