Santiago Guzmán-Pro gave an online talk on characterizing hereditary graph classes definable by forbidden orientations at the Virtual Discrete Math Colloquium 

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“.

Santiago Guzmán-Pro, 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.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.