Events items teaser

Hitting all maximum stable sets in P5-free graphs - Sepehr Hajebi
2023-02-06 15:00 (America/Toronto)
TITLE: Hitting all maximum stable sets in P5-free graphs

Speaker:
Sepehr Hajebi

Institution:
University of Waterloo

Location:
MC 5479

ABSTRACT: We prove that there exists a function f such that, for
every positive integer c, every graph with no induced five-vertex path
contains either a clique on c+1 vertices or a set of at most f(c)
vertices which intersects all maximum stable sets in G.
