기초과학연구원 이산수학그룹
On September 29, 2022, Santiago Guzmán-Pro from the Universidad Nacional Autónoma de México (UNAM), Mexico gave an online talk on characterizing hereditary graph classes definable by forbidden orientations at the Virtual Discrete Math Colloquium. The title of his talk was “Local expressions of graphs classes“.
A common technique to characterize hereditary graph classes is to exhibit their minimal obstructions. Sometimes, the set of minimal obstructions might be infinite, or too complicated to describe. For instance, for any $k\ge 3$, the set of minimal obstructions of the class of $k$-colourable graphs is yet unknown. Nonetheless, the Roy-Gallai-Hasse-Vitaver Theorem asserts that a graph $G$ is $k$-colourable if and only if it admits an orientation with no directed walk on $k+1$ vertices. We say that a class of graphs $\mathcal{P}$ is expressible by forbidden orientations if there is a finite set $F$ of oriented graphs such that $\mathcal{P}$ is the class of graphs that admit an $F$-free orientation. We are interested in understanding which graph classes are expressible by forbidden orientations (and why). In this talk, we present some limitations of this expression system. In particular, we show that the class of even-hole free graphs is not expressible by forbidden orientations.
Throughout the talk, we also mention some other related expression systems. In particular, each of these systems provides a certification method to the $\mathcal{P}$-decision problem; i.e., decide if an input graph belongs to the class $\mathcal{P}$. We conclude this talk by proposing a general framework to talk about these expression systems. This framework allows us to formalize the question, what can be certified this way?
Based on a joint work with César Hernández-Cruz.