Graph transversals

• Grant number: 15/08538-5
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: September 01, 2015
• End date: 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

Abstract

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.

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., 2018-01-01. (15/08538-5)

GUTIERREZ, JUAN. ransversals of longest cycles in partial k-trees and chordal graph. JOURNAL OF GRAPH THEORY, v. 98, n. 4, JUL 2021. (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, MAR 2020. (13/03447-6, 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, APR 2021. (13/03447-6, 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., 2023-03-01. (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., 2019-08-30. (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.