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: