Donggyu Kim (김동규), A stronger version of Tutte’s wheel theorem for vertex-minors
Room B232 IBS (기초과학연구원)Tutte (1961) proved that every simple
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 each fixed finite field
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 there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. By …
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, is either Hamiltonian or contains a cycle of length at least 2d. Second, the theorem of Erdős-Gallai from 1959, states that a 2-connected graph G …
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
The first-order model checking problem for finite graphs asks, given a graph G and a first-order sentence