Manuel Lafond, Recognizing k-leaf powers in polynomial time, for constant k
Zoom ID: 869 4632 6610 (ibsdimag)A graph G is a k-leaf power if there exists a tree T whose leaf set is V(G), and such that uv is an edge if and only if the …
10 events found.
Seminars and Colloquiums
-
-
-
Donggyu Kim (김동규), A stronger version of Tutte’s wheel theorem for vertex-minors
Room B232 IBS (기초과학연구원)Tutte (1961) proved that every simple $3$-connected graph $G$ has an edge $e$ such that $G \setminus e$ or $G / e$ is simple $3$-connected, unless $G$ is isomorphic to …
-
Sang-il Oum (엄상일), Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k
Room B232 IBS (기초과학연구원)Every minor-closed class of matroids of bounded branch-width can be characterized by a minimal list of excluded minors, but unlike graphs, this list could be infinite in general. However, for …
-
-
Kevin Hendrey, A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups (revisited)
Room B232 IBS (기초과학연구원)This talk follows on from the recent talk of Pascal Gollin in this seminar series, but will aim to be accessible for newcomers. Erdős and Pósa proved in 1965 that …
-
Fedor Fomin, Long cycles in graphs: Extremal Combinatorics meets Parameterized Algorithms
Zoom ID: 869 4632 6610 (ibsdimag)We examine algorithmic extensions of two classic results of extremal combinatorics. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree d>1, …
-
Tuan Anh Do, Rank- and tree-width of supercritical random graphs
Room B232 IBS (기초과학연구원)It is known that the rank- and tree-width of the random graph $G(n,p)$ undergo a phase transition at $p = 1/n$; whilst for subcritical $p$, the rank- and tree-width are bounded above …
-
Jaehoon Kim (김재훈), Ramsey numbers of cycles versus general graphs
Room B232 IBS (기초과학연구원)The Ramsey number $R(F,H)$ is the minimum number $N$ such that any $N$-vertex graph either contains a copy of $F$ or its complement contains $H$. Burr in 1981 proved a …
-
Ben Lund, Thresholds for incidence properties in finite vector spaces
Room B232 IBS (기초과학연구원)Suppose that $E$ is a subset of $\mathbb{F}_q^n$, so that each point is contained in $E$ with probability $\theta$, independently of all other points. Then, what is the probability that …
-
Jean-Florent Raymond, Long induced paths in minor-closed graph classes and beyond
Zoom ID: 869 4632 6610 (ibsdimag)In 1982 Galvin, Rival, and Sands proved that in $K_{t,t}$-subgraph free graphs (t being fixed), the existence of a path of order n guarantees the existence of an induced path …
-
-
Younjin Kim (김연진), On the extremal problems related to Szemerédi’s theorem
Room B232 IBS (기초과학연구원)In 1975, Szemerédi proved that for every real number $\delta > 0 $ and every positive integer $k$, there exists a positive integer $N$ such that every subset $A$ of …