Orthogonality of packings of paths and independent sets partitions on bipartite gr...

Algorithmic and structural aspects of covering and packing problems on graphs

Send your message by email

Advanced search

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 |

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: | |

TITULO | |

Articles published in other media outlets (0 total):
| |

More itemsLess items | |

VEICULO: TITULO (DATA) | |

VEICULO: TITULO (DATA) | |

Scientific publications
(7)

(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; SAMBINELLI, MAYCON. Towards Gallai's path decomposition conjecture.** JOURNAL OF GRAPH THEORY**, v. 97, n. 1, NOV 2020. (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; 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)

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, 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)

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)

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)

Please report errors in scientific publications list by writing to:
gei-bv@fapesp.br.