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

• Processo: 17/23623-4
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Data de Início da vigência: 01 de maio de 2018
• Data de Término da vigência: 31 de agosto de 2019
• Área de 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)

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., 2021-01-01. (15/11937-9, 19/13364-7, 17/23623-4)

SAMBINELLI, M.; NUNES DA SILVA, C.; LEE, O.. alpha-Diperfect digraphs. DISCRETE MATHEMATICS, v. 345, n. 5, p. 12-pg., 2022-05-01. (15/11937-9, 17/23623-4)

BOTLER, FABIO; SAMBINELLI, MAYCON. Towards Gallai's path decomposition conjecture. JOURNAL OF GRAPH THEORY, v. 97, n. 1, NOV 2020. (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, MAY 2019. (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., 2019-08-16. (17/23623-4, 15/11937-9, 13/03447-6)

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. (17/23623-4, 13/03447-6, 15/11937-9)

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. (17/23623-4)

LINTZMAYER, C. N.; MOTA, G. O.; SAMBINELLI, M.. Decomposing split graphs into locally irregular graphs. DISCRETE APPLIED MATHEMATICS, v. 292, p. 33-44, MAR 31 2021. (17/23623-4, 18/04876-1, 13/03447-6)

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., 2019-08-30. (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., 2019-08-30. (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., 2019-08-30. (17/23623-4)