J. Rauch

activity

20222026

most citedRevisiting Extremal Graphs Having No Stable Cutsets

1 citations · 1 across the 10 of their papers we have counts for

collaborators

Showing math.COShow all

4 papers · 1 filter

math.CO2026

Degenerate Vertex Cuts in Sparse Graphs

Thilo Hartel, Johannes Rauch, Dieter Rautenbach

For a non-negative integer $k$ , a vertex cut in a graph is $k$ -degenerate if it induces a $k$ -degenerate subgraph. We show that a graph of order $n$ at least $2 k + 2$ without a $k$ -d…

math.CO2024★ 1 cited

Revisiting Extremal Graphs Having No Stable Cutsets

Johannes Rauch, Dieter Rautenbach

Confirming a conjecture posed by Caro, it was shown by Chen and Yu that every graph $G$ with $n$ vertices and at most $2 n - 4$ edges has a stable cutset, which is a stable set of ver…

math.CO2024

Forest Cuts in Sparse Graphs

Vsevolod Chernyshev, Johannes Rauch, Dieter Rautenbach

We propose the conjecture that every graph $G$ of order $n$ with less than $3 n - 6$ edges has a vertex cut that induces a forest. Maximal planar graphs do not have such vertex cuts a…

math.CO2022

Efficiently recognizing graphs with equal independence and annihilation numbers

Johannes Rauch, Dieter Rautenbach

The annihilation number $a (G)$ of a graph $G$ is an efficiently computable upper bound on the independence number $α (G)$ of $G$ . Recently, Hiller observed that a characterization o…