기초과학연구원 이산수학그룹
Tree decompositions are a powerful tool in structural graph theory; they are traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has until recently remained out of reach. Tree decompositions are closely related to the existence of "laminar collections of separations" in a graph, which roughly means that …
Tree decompositions are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition of bounded “width”. Exhibiting a particular kind of a tree decomposition is also a useful way to describe the structure of a graph. Tree decompositions …
We will discuss recent progress on the topic of induced subgraphs and tree-decompositions. In particular this talk with focus on the proof of a conjecture of Hajebi that asserts that (if we exclude a few obvious counterexamples) for every integer t, every graph with large enough treewidth contains two anticomplete induced subgraphs each of treewidth …
This talk deals with induced minor obstructions to treewidth. The natural setup for this problem is to consider the class of graphs excluding some planar graph, and some complete bipartite graph as induced minors, and some complete graph as a subgraph. Unfortunately, such classes still contain graphs of arbitrarily large treewidth. Moreover, a result of …