Busca avançada
Ano de início
Entree

Problemas de partição em grafos e dígrafos

Processo: 17/23623-4
Linha de fomento:Bolsas no Brasil - Pós-Doutorado
Vigência (Início): 01 de maio de 2018
Vigência (Término): 31 de agosto de 2019
Área do conhecimento:Ciências Exatas e da Terra - Matemática
Pesquisador responsável:Yoshiko Wakabayashi
Beneficiário:Maycon Sambinelli
Instituição-sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
Vinculado ao auxílio:15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural, AP.TEM
Assunto(s):Teoria dos grafos   Dígrafos   Partições

Resumo

Este é o projeto de pesquisa para o pós-doutorado de Maycon Sambinelli, a ser desenvolvido sob a supervisão de Yoshiko Wakabayashi, no Instituto de Matemática e Estatística da Universidade de São Paulo. Este projeto se insere na área de teoria estrutural dos grafos e tem por objetivo estudar problemas clássicos de partição em grafos e dígrafos. Pretendemos investigar problemas sobre partição dos vértices de um (dí)grafo, e também problemas sobre partição das arestas de um (dí)grafo que satisfazem certas propriedades. Como exemplo citamos o seguinte problema, proposto por Linial em 1981. Seja D um dígrafo, k um inteiro positivo, P uma coleção de caminhos disjuntos nos vértices que cobre os vértices de D e que minimiza \pi_k(D) = \sum_{P_i \in P} min{|V(P_i)|, k}, e seja C uma coleção de até k conjuntos independentes disjuntos nos vértices de D que maximiza \chi_k(D) = \sum_{C_i \in C} |C_i|. Provar que a relação \pi_k(D) \leq \chi_k(D) é válida para todo dígrafo D. Um outro problema de nosso interesse é provar (ou desprovar) que as arestas de um grafo G de ordem n podem ser cobertas usando-se no máximo (n + 1)/2 caminhos disjuntos nas arestas. Provas da validade desse limite (conjecturado por Gallai na década de 60) são conhecidas para algumas classes de grafos; temos interesse em ampliar tais classes. Nessa busca por resultados dessa natureza, esperamos contribuir com técnicas de provas inovadoras que avancem o estado da arte. (AU)

Publicações científicas
(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)
BOTLER, FABIO; SAMBINELLI, MAYCON; COELHO, RAFAEL S.; LEE, ORLANDO. Gallai's path decomposition conjecture for graphs with treewidth at most 3. JOURNAL OF GRAPH THEORY, AUG 2019. Citações Web of Science: 0.
BOTLER, F.; JIMENEZ, A.; SAMBINELLI, M. Gallai's path decomposition conjecture for triangle-free planar graphs. DISCRETE MATHEMATICS, v. 342, n. 5, p. 1403-1414, MAY 2019. Citações Web of Science: 2.
BOTLER, F.; SAMBINELLI, M. GALLAI'S PATH DECOMPOSITION CONJECTURE FOR GRAPHS WITH MAXIMUM E-DEGREE AT MOST 3. ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, v. 88, n. 3, p. 501-505, 2019. Citações Web of Science: 0.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.
Mapa da distribuição dos acessos desta página
Para ver o sumário de acessos desta página, clique aqui.