Hidde Koerts, Characterizing large clique number in tournaments
A backedge graph of a tournament $T$ with respect to a total ordering $\prec$ of the vertices of $T$ is a graph on $V(T)$ where $uv$ is an edge if …
10 events found.
Events
-
-
Room B332 IBS (기초과학연구원)
-
Tung H. Nguyen, Polynomial χ-boundedness for excluding the five-vertex path
Room B332 IBS (기초과학연구원)We overview the recent resolution of a 1985 open problem of Gyárfás, that chromatic number is polynomially bounded by clique number for graphs with no induced five-vertex path. The proof …
-
-
Mamadou Moustapha Kanté, Strongly flip-flat classes of graphs
Room B332 IBS (기초과학연구원)Strong flip-flatness appears to be the analogue of uniform almost-wideness in the setting of dense classes of graphs. Almost-wideness is a notion that was central in different characterisations of nowhere …
-
Xin Wei, Separating hash families with large universe
Room B332 IBS (기초과학연구원)Separating hash families are useful combinatorial structures that generalize several well-studied objects in cryptography and coding theory. Let $p_t(N, q)$ denote the maximum size of the universe for a $t$-perfect …
-
-
Maximilian Gorsky, The Disjoint Paths Problem lies in the Oort cloud of algorithms
Room B332 IBS (기초과학연구원)In this talk we discuss recent work to that establishes that the bounds of the Vital Linkage Function is single-exponential. This has immediate impacts on the complexity of the k-Disjoint …
-
Benjamin Duhamel, Excluding a forest induced minor
Room B332 IBS (기초과학연구원)We give an induced counterpart of the Forest Minor theorem: for any t ≥ 2, the $K_{t,t}$-subgraph-free H-induced-minor-free graphs have bounded pathwidth if and only if H belongs to a …
-
Xavier Goaoc, TBA
Room B332 IBS (기초과학연구원) -
Sarah Morell, Unsplittable Transshipments
Room B332 IBS (기초과학연구원)We consider an arc-capacitated directed graph $D=(V,A)$, where each node $v$ is associated with a rational balance value $b(v)$. Nodes with negative balance values are referred to as sources, while …
-
-
Maria Chudnovsky, TBA
Room B332 IBS (기초과학연구원) -
Martin Milanič, TBA
Room B332 IBS (기초과학연구원)