기초과학연구원 이산수학그룹
On June 11, 2024, Maria Chudnovsky from Princeton University gave a talk at the Discrete Math Seminar on finding the disjoint union of two graphs of large treewidth as an induced subgraph. The title of her talk was “Anticomplete subgraphs of large treewidth“.
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 at least t. This is joint work with Sepher Hajebi and Sophie Spirkl.
On May 11, 2023, Maria Chudnovsky from Princeton University gave a colloquium talk held at KAIST about bounding the tree-width of graphs by forbidding induced subgraphs. The titlte of her talk was “Induced subgraphs and tree decompositions.”
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 have traditionally been used in the context of forbidden graph minors; bringing them into the realm of forbidden induced subgraphs has until recently remained out of reach. Over the last couple of years we have made significant progress in this direction, exploring both the classical notion of bounded tree-width, and concepts of more structural flavor. This talk will survey some of these ideas and results.
On July 28, 2021, Maria Chudnovsky from Princeton University gave an online talk at the Virtual Discrete Math Colloquium on structural aspects of graphs of large tree-width in terms of induced subgraphs. The title of her talk was “Induced subgraphs and tree decompositions“.
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 the separations in the collection “cooperate” with each other, and the pieces that are obtained when the graph is simultaneously decomposed by all the separations in the collection “line up” to form a tree structure. Such collections of separations come up naturally in the context of forbidden minors.
In the case of families where induced subgraphs are excluded, while there are often natural separations, they are usually very far from forming a laminar collection. In what follows we mostly focus on families of graphs of bounded degree. It turns out that due to the bound on the degree, these collections of natural separations can be partitioned into a bounded number of laminar collections. This in turn allows to us obtain a wide variety of structural and algorithmic results, which we will survey in this talk.