Universidad Nacional Autónoma de México, Mexico.
Title: Revisiting full homomorphisms
Abstract: For a pair of graphs $G$ and $H$, a \textit{homomorphism} from $G$ to $H$ is a function $f \colon V_G \to V_H$ that preserves adjacencies, i.e., for any pair of vertices $u$ and $v$ of $G$, the existence of the edge $uv$ in $G$ implies the existence of the edge $f(u)f(v)$ in $H$. A homomorphism is \textit{full} if it also preserves non-adjacencies (the converse implication in the definition of homomorphism also holds). When $H$ is a fixed graph, the problem of determining, for an input graph $G$, the existence of a full homomorphism to $H$, is often called the full $H$-homomorphism problem or the full $H$-colouring problem. From the complexity point of view, the full $H$-colouring problem has been solved: For any fixed graph $H$, the full $H$-colouring problem is polynomial-time solvable. This classification has deterred further study on full homomorphisms, so little is known in terms of the fine-grained complexity of this problem. In this talk, we will discuss the full $H$-colouring problem when $H$ belongs to some simple families of graphs, showing that really nice complexities can be obtained in some cases.
Short bio: César received bachelor degrees in Mathematics and Computer Science at the National Autonomous University of México (UNAM), and M.Sc. and Ph.D. degrees in Mathematics at the same university. After holding postdoctoral positions at Simon Fraser University in Canada and at UNAM in México, he was a Catedrático CONACYT commissioned to the Autonomous University of Zacatecas and afterwards a CINVESTAV Researcher at the Centre of Research and Advanced Studies of the National Polytechnic Institute in México City. Since December 2019, he is an Associate Professor at the Department of Mathematics in the Faculty of Sciences, UNAM. Although in later years he has worked mainly with hereditary properties of graphs and digraphs, including characterizations, algorithmic and complexity aspects, he has done research in a wide variety of subjects, and keeps an open mind about all areas of graph theory.
Teaching is César’s main activity, besides teaching a broad spectrum of courses in Mathematics and Computer Science, in both undergraduate and graduate programs, he enjoys the personal collaborations that arise in thesis supervisions. He has supervised 14 undergraduate, 6 master and 3 Ph.D. theses; he is currently supervising 6 undergraduate and 1 master theses, as well as a postdoc.
In 2022, César was admitted as a regular member of the Mexican Academy of Sciences, and he was recently appointed as a member of the Editorial Board of Ars Combinatoria.
