Advanced search
Start date

Graph transversals

Grant number: 15/08538-5
Support Opportunities:Scholarships in Brazil - Doctorate
Effective date (Start): September 01, 2015
Effective date (End): August 31, 2018
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Cristina Gomes Fernandes
Grantee:Juan Gabriel Gutierrez Alva
Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
Associated research grant:13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science, AP.TEM


In graph theory, a classic problem consists in finding a set of vertex or edges such that every object of some kind contains at least one element in that set. Such a set is called transversal, and in general we try to search little transversals, possibly of minimum size.When we don't know the size of a minimum transversal, it is interesting to search for good delimitations for that size. When finding a minimum transversal is NP-hard, we try to find approximations for the problem. The target of this project are some kinds of transversals in graphs, for example transversal of longest paths, of longest cycles, of odd-cycles, and maximal cliques. The goal is to find the size of minimum transversals for these objects in arbitrary or specific classes of graphs.

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

Scientific publications (6)
(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)
GUTIERREZ, JUAN; BENDER, MA; FARACHCOLTON, M; MOSTEIRO, MA. Transversals of Longest Cycles in Chordal and Bounded Tree-Width Graphs. LATIN 2018: THEORETICAL INFORMATICS, v. 10807, p. 14-pg., . (15/08538-5)
BOTLER, FABIO; FERNANDES, CRISTINA G.; GUTIERREZ, JUAN. On Tuza's conjecture for triangulations and graphs with small treewidth. DISCRETE MATHEMATICS, v. 344, n. 4, . (13/03447-6, 15/08538-5)
GUTIERREZ, JUAN. ransversals of longest cycles in partial k-trees and chordal graph. JOURNAL OF GRAPH THEORY, v. 98, n. 4, . (15/08538-5)
CERIOLI, MARCIA R.; FERNANDES, CRISTINA G.; GOMEZ, RENZO; GUTIERREZ, JUAN; LIMA, PALOMA T.. Transversals of longest paths. DISCRETE MATHEMATICS, v. 343, n. 3, . (13/03447-6, 15/08538-5)
BOTLER, F.; FERNANDES, C. G.; GUTIERREZ, J.. On Tuza's Conjecture for Triangulations and Graphs with Small Treewidth. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 346, p. 13-pg., . (15/08538-5)
GUTIERREZ, JUAN. All longest cycles in a 2-connected partial 3-tree share a common vertex. JOURNAL OF GRAPH THEORY, v. 103, n. 4, p. 23-pg., . (15/08538-5)
Academic Publications
(References retrieved automatically from State of São Paulo Research Institutions)
ALVA, Juan Gabriel Gutierrez. Transversals of graphs. 2018. Doctoral Thesis - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.

Please report errors in scientific publications list using this form.