Busca avançada
Ano de início
Entree

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

Processo: 17/23623-4
Modalidade de apoio: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
Palavra(s)-Chave do Pesquisador:Decomposição em caminhos ou ciclos | Número de estabilidade acíclica de digrafo | Partição de grafos | Partição em conjuntos independentes | Teoria dos Grafos

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)

Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa:
Matéria(s) publicada(s) em Outras Mídias (0 total):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Publicações científicas (11)
(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; JIMENEZ, ANDREA; SAMBINELLI, MAYCON; WAKABAYASHI, YOSHIKO; FERREIRA, CE; LEE, O; MIYAZAWA, FK. The 2-Decomposition Conjecture for a new class of graphs. PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, v. 195, p. 9-pg., . (15/11937-9, 19/13364-7, 17/23623-4)
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, . (17/23623-4)
BOTLER, FABIO; SAMBINELLI, MAYCON. Towards Gallai's path decomposition conjecture. JOURNAL OF GRAPH THEORY, v. 97, n. 1, . (17/23623-4)
SAMBINELLI, M.; NUNES DA SILVA, C.; LEE, O.. alpha-Diperfect digraphs. DISCRETE MATHEMATICS, v. 345, n. 5, p. 12-pg., . (15/11937-9, 17/23623-4)
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, v. 93, n. 3, p. 22-pg., . (17/23623-4, 15/11937-9, 13/03447-6)
LINTZMAYER, C. N.; MOTA, G. O.; SAMBINELLI, M.. Decomposing split graphs into locally irregular graphs. DISCRETE APPLIED MATHEMATICS, v. 292, p. 33-44, . (17/23623-4, 18/04876-1, 13/03447-6)
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, . (17/23623-4)
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, . (17/23623-4, 13/03447-6, 15/11937-9)
LINTZMAYER, C. N.; MOTA, G. O.; SAMBINELLI, M.. Decomposing Split Graphs into Locally Irregular Graphs. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 346, p. 10-pg., . (18/04876-1, 17/23623-4, 13/03447-6)
YOSHIMURA, LUCAS R.; SAMBINELLI, MAYCON; DA SILVA, CANDIDA N.; LEE, ORLANDO. Linial's Conjecture for Arc-spine Digraphs. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 346, p. 12-pg., . (17/21345-7, 17/23623-4, 15/11937-9)
BOTLER, F.; CANO, R.; SAMBINELLI, M.. On Computing the Path Number of a Graph. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 346, p. 13-pg., . (17/23623-4)

Por favor, reporte erros na lista de publicações científicas utilizando este formulário.