Zobrazeno 1 - 10
of 64
pro vyhledávání: '"05C75, 05C83"'
Let $\mathcal{H}$ be a graph class and $k\in\mathbb{N}$. We say a graph $G$ admits a \emph{$k$-identification to $\mathcal{H}$} if there is a partition $\mathcal{P}$ of some set $X\subseteq V(G)$ of size at most $k$ such that after identifying each p
Externí odkaz:
http://arxiv.org/abs/2409.08883
Given a graph $G$ and a vertex set $X$, the annotated treewidth tw$(G,X)$ of $X$ in $G$ is the maximum treewidth of an $X$-rooted minor of $G$, i.e., a minor $H$ where the model of each vertex of $H$ contains some vertex of $X$. That way, tw$(G,X)$ c
Externí odkaz:
http://arxiv.org/abs/2406.18465
We revisit a graph width parameter that we dub bipartite treewidth, along with its associated graph decomposition that we call bipartite tree decomposition. Bipartite treewidth can be seen as a common generalization of treewidth and the odd cycle tra
Externí odkaz:
http://arxiv.org/abs/2309.07754
Autor:
Carmesin, Johannes, Kurkofka, Jan
We offer a new structural basis for the theory of 3-connected graphs, providing a unique decomposition of every such graph into parts that are either quasi 4-connected, wheels, or thickened $K_{3,m}$'s. Our construction is explicit, canonical, and ha
Externí odkaz:
http://arxiv.org/abs/2304.00945
We show that a graph contains a large wall as a strong immersion minor if and only if the graph does not admit a tree-cut decomposition of small `width', which is measured in terms of its adhesion and the path-likeness of its torsos.
Comment: 15
Comment: 15
Externí odkaz:
http://arxiv.org/abs/2301.05134
We show that every $3$-connected $K_{2,\ell}$-minor free graph with minimum degree at least $4$ has maximum degree at most $7\ell$. As a consequence, we show that every 3-connected $K_{2,\ell}$-minor free graph with minimum degree at least $5$ and no
Externí odkaz:
http://arxiv.org/abs/2301.02133
Autor:
Singh, Jagdeep
A graph that can be generated from $K_1$ using joins and 0-sums is called a cograph. We define a sesquicograph to be a graph that can be generated from $K_1$ using joins, 0-sums, and 1-sums. We show that, like cographs, sesquicographs are closed unde
Externí odkaz:
http://arxiv.org/abs/2210.04139
Autor:
Carmesin, Johannes
A graph $H$ is ubiquitous if for every graph $G$ that for every natural number $n$ contains $n$ vertex-disjoint $H$-minors contains infinitely many vertex-disjoint $H$-minors. Andreae conjectured that every locally finite graph is ubiquitous. We give
Externí odkaz:
http://arxiv.org/abs/2210.02711
Publikováno v:
TheoretiCS, Volume 3 (August 12, 2024) theoretics:11623
Let ${\cal G}$ be a minor-closed graph class and let $G$ be an $n$-vertex graph. We say that $G$ is a $k$-apex of ${\cal G}$ if $G$ contains a set $S$ of at most $k$ vertices such that $G\setminus S$ belongs to ${\cal G}$. Our first result is an algo
Externí odkaz:
http://arxiv.org/abs/2210.02167
Autor:
Kim, Donggyu, Oum, Sang-il
Publikováno v:
European J. Combin., 118:103871, May 2024
A graph is prime if it does not admit a partition $(A,B)$ of its vertex set such that $\min\{|A|,|B|\} \geq 2$ and the rank of the $A\times B$ submatrix of its adjacency matrix is at most $1$. A vertex $v$ of a graph is non-essential if at least two
Externí odkaz:
http://arxiv.org/abs/2202.07877