-
Article
A Polynomial Kernel for 3-Leaf Power Deletion
For a non-negative integer \(\ell \) ℓ , the
-
Article
\(\Gamma \) -Graphic Delta-Matroids and Their Applications
For an abelian group \(\Gamma \) Γ , a
-
Article
Tangle-Tree Duality: In Graphs, Matroids and Beyond
We apply a recent tangle-tree duality theorem in abstract separation systems to derive tangle-tree-type duality theorems for width-parameters in graphs and matroids.We further derive a duality theorem for the ...
-
Article
Defective Colouring of Graphs Excluding A Subgraph or Minor
Archdeacon (1987) proved that graphs embeddable on a fixed surface can be 3-coloured so that each colour class induces a subgraph of bounded maximum degree. Edwards, Kang, Kim, Oum and Seymour (2015) proved th...
-
Article
A Remark on the Paper “Properties of Intersecting Families of Ordered Sets” by O. Einstein
O. Einstein (2008) proved Bollobás-type theorems on intersecting families of ordered sets of finite sets and subspaces. Unfortunately, we report that the proof of a theorem on ordered sets of subspaces had a m...
-
Article
An FPT 2-Approximation for Tree-Cut Decomposition
The tree-cut width of a graph is a graph parameter defined by Wollan (J Combin Theory, Ser B, 110:47–66, 2015) with the help of tree-cut decompositions. In certain cases, tree-cut width appears to be more adequat...
-
Chapter and Conference Paper
Computing Small Pivot-Minors
A graph G contains a graph H as a pivot-minor if H can be obtained from G by applying a sequence of vertex deletions and edge pivots. Pivot-minors play an important role in the study of rank-width. However, so fa...
-
Chapter and Conference Paper
An FPT 2-Approximation for Tree-cut Decomposition
The tree-cut width of a graph is a graph parameter defined by Wollan [J. Comb. Theory, Ser. B, 110:47–66, 2015] with the help of tree-cut decompositions. In certain cases, tree-cut width appears to be more adequa...
-
Chapter and Conference Paper
Unifying Duality Theorems for Width Parameters in Graphs and Matroids (Extended Abstract)
We prove a general duality theorem for width parameters in combinatorial structures such as graphs and matroids. It implies the classical such theorems for path-width, tree-width, branch-width and rank-width, ...
-
Article
Finding minimum clique capacity
Let C be a clique of a graph G. The capacity of C is defined to be (|V (G)\C|+|D|)/2, where D is the set of vertices in V (G)\C that have both a neighbour and a non-neighbour in C. We give a polynomial-time algor...
-
Chapter and Conference Paper
Deciding First Order Properties of Matroids
Frick and Grohe [J. ACM 48 (2006), 1184–1206] introduced a notion of graph classes with locally bounded tree-width and established that every first order property can be decided in almost linear time in such a...
-
Chapter and Conference Paper
Finding Branch-Decompositions and Rank-Decompositions
We present a new algorithm that can output the rank-decomposition of width at most k of a graph if such exists. For that we use an algorithm that, for an input matroid represented over a fixed finite field, outpu...
-
Chapter and Conference Paper
Approximating Rank-Width and Clique-Width Quickly
Rank-width is defined by Seymour and the author to investigate clique-width; they show that graphs have bounded rank-width if and only if they have bounded clique-width. It is known that many hard graph proble...
