Pascal Gollin, A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups

Room B232 IBS (기초과학연구원)

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. We therefore say that cycles satisfy the Erdős-Pósa property. However, while odd cycles do not satisfy the Erdős-Pósa property, Reed proved in 1999 an analogue by

James Davies, Separating polynomial $\chi$-boundedness from $\chi$-boundedness

Zoom ID: 869 4632 6610 (ibsdimag)

We prove that there is a function $f : \mathbb{N} \to \mathbb{N}$ such that for every function $g : \mathbb{N} \to \mathbb{N} \cup \{\infty\}$ with $g(1)=1$ and $g \ge f$, there is a hereditary class of graphs $\mathcal{G}$ such that for each $\omega \in \mathbb{N}$, the maximum chromatic number of a graph in $\mathcal{G}$ with

Jinha Kim (김진하), Independent domination of graphs with bounded maximum degree

Room B232 IBS (기초과학연구원)

An independent dominating set of a graph, also known as a maximal independent set, is a set $S$ of pairwise non-adjacent vertices such that every vertex not in $S$ is adjacent to some vertex in $S$. We prove that for $\Delta=4$ or $\Delta\ge 6$, every connected $n$-vertex graph of maximum degree at most $\Delta$ has

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 a wheel. We call such an edge non-essential. Oxley and Wu (2000) proved that every simple $3$-connected graph has at least $2$ non-essential edges unless

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 each fixed finite field $\mathbb F$, the list contains only finitely many $\mathbb F$-representable matroids, due to the well-quasi-ordering of $\mathbb F$-representable matroids of bounded

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 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

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, 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

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 by a constant, for supercritical $p$, both parameters are linear in $n$. The known proofs of these results use as a black box an important theorem of

MATRIX-IBS Workshop: Structural Graph Theory Downunder II

MATRIX, Australia

This program consists of a short intensive workshop, where mathematicians from across the globe will come together to work on open problems in structural graph theory. We will consider the following research themes: graph minors, graph colouring, Hadwiger’s Conjecture, bounded expansion classes, graph product structure theory, generalised colouring numbers, VC dimension, induced subgraphs, Erdős-Hajnal conjecture,

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.