This is a proposal for a research internship of Phablo Fernando Soares Moura (FAPESP Proc. 2016/21250-3), postdoctoral researcher under supervision of Professor Flávio Keidi Miyazawa at the Instituto de Computação at Universidade Estadual de Campinas. This internship, to be held at Charles University in Prague, the Czech Republic, is planned from August 1, 2018 to July 31, 2019 (12 months). During this period, Phablo will be supervised by Professor Zdenek Dvorak. The focus of this research proposal is the study of covering and packing problems on graphs and digraphs. We are particularly interested in studying the path cover problem, the Four-Color problem, and problems concerning the Mader's conjecture about subdivisions of digraphs. In the first problem, we are interested in covering the set of vertices of a graph into a minimum number of vertex-disjoint paths. In the second problem, we study the reducibility of configurations for the Four-Color theorem. Finally, in the context of Mader's conjecture, we aim to find sufficient conditions for a digraph to contain an acyclic digraph as a subdivision.
News published in Agência FAPESP Newsletter about the scholarship: