Benjamin Bergougnoux, Tight Lower Bounds for Problems Parameterized by Rank-width
Zoom ID: 869 4632 6610 (ibsdimag)We show that there is no
We show that there is no
Hadwiger's famous coloring conjecture states that every t-chromatic graph contains a
A circle graph is an intersection graph of a set of chords of a circle. In this talk, I will describe the unavoidable induced subgraphs of circle graphs with large treewidth. This includes examples that are far from the `usual suspects'. Our results imply that treewidth and Hadwiger number are linearly tied on the class …
We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph
Let
Let
Given an undirected planar graph
A subset
We give a summary on the work of the last months related to Frankl's Union-Closed conjecture and its offsprings. The initial conjecture is stated as a theorem in extremal set theory; when a family F is union-closed (the union of sets of F is itself a set of
In 1977, Erdős and Hajnal made the conjecture that, for every graph