Advanced search
Start date
Betweenand

Partition problems in graphs and digraphs

Grant number: 17/23623-4
Support Opportunities:Scholarships in Brazil - Post-Doctoral
Effective date (Start): May 01, 2018
Effective date (End): August 31, 2019
Field of knowledge:Physical Sciences and Mathematics - Mathematics
Principal Investigator:Yoshiko Wakabayashi
Grantee:Maycon Sambinelli
Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
Associated research grant:15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points, AP.TEM

Abstract

This is the research project for the postdoctoral fellowship of Maycon Sambinelli, to be carried out under the supervision of Yoshiko Wakabayashi, at the Instituto de Matemática e Estatística of the University of São Paulo. This project addresses topics on structural graph theory, more specifically, classical partition problems in graphs and digraphs. We plan to investigate problems on vertex-partition and edge-partition. As an example, we mention a problem proposed by Linial in 1981. Let D be a digraph, k a positive integer, P a collection of vertex-disjoint paths which covers V(D) and minimizes \pi_k(D) = \sum_{P_i \in P} min{|V(P_i)|, k}, and let C be a collection of at most k disjoint stable sets which maximize \chi_k(D) = \sum_{C_i \in C} |C_i|. Prove that the relation \pi_k(D) \leq \alpha_k(D) holds for every digraph D. As an example of a problem on edge-partition, we mention the problem of verifying whether it is always possible to cover the edges of a given n-vertex graph G using at most (n + 1)/2 edge-disjoint paths. This upper bound was conjectured by Gallai in the late sixties, and has been proved for some classes of graphs. We expect to expand such classes, and also to contribute with new proof techniques to advance the state of the art of the field. (AU)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Scientific publications (11)
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
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)
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, 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)
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)
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)
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)
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)
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)

Please report errors in scientific publications list using this form.