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 …
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 …
Tutte (1961) proved that every simple
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 …
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 …
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, …
It is known that the rank- and tree-width of the random graph
The Ramsey number
Suppose that
In 1982 Galvin, Rival, and Sands proved that in
In 1975, Szemerédi proved that for every real number