Loading Events

« All Events

  • This event has passed.

Santiago Guzmán-Pro, Local expressions of graphs classes

September 29 Thursday @ 10:00 AM - 11:00 AM KST

Zoom ID: 869 4632 6610 (ibsdimag)


Santiago Guzmán-Pro
UNAM, Mexico

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.


September 29 Thursday
10:00 AM - 11:00 AM KST
Event Category:
Event Tags:


Zoom ID: 869 4632 6610 (ibsdimag)


O-joung Kwon (권오정)
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.