권오정

Vatshelle (2012) introduced a width parameter called mim-width. It is based on the following cut function : for a vertex partition (A,B) of a graph, the complexity of this partition is computed by the size of a maximum induced matching of the bipartite subgraph induced by edges between A and B. This parameter naturally extends …

The canonical tree-decomposition theorem, proved by Robertson and Seymour in their seminal graph minors series, turns out to be an extremely valuable tool in structural and algorithmic graph theory. In this paper, we prove the analogous result for digraphs, the directed tangle tree-decomposition theorem. More precisely, we introduce directed tangles and provide a directed tree-decomposition …

An intersection digraph is a digraph where every vertex $v$ is represented by an ordered pair $(S_v,T_v)$ of sets such that there is an edge from $v$ to $w$ if and only if $S_v$ and $T_w$ intersect. An intersection digraph is reflexive if $S_v\cap T_v\ne \mathrm{\varnothing }$ for every vertex $v$. Compared to well-known undirected …

In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying $u$ and $v$, each edge incident to exactly one of $u$ and $v$ is coloured red. Bonnet, Kim, Thomassé, and Watrigant defined the twin-width of a graph $G$ to be the minimum integer …

A family $\mathcal{F}$ of graphs is said to satisfy the Erdős-Pósa property if there exists a function $f$ such that for every positive integer $k$, every graph $G$ contains either $k$ (vertex-)disjoint subgraphs in $\mathcal{F}$ or a set of at most $f(k)$ vertices intersecting every subgraph of $G$ in $\mathcal{F}$. We characterize the obstructions to …