Dieter Rautenbach

activity

20232026

most citedRevisiting Extremal Graphs Having No Stable Cutsets

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

collaborators

16 papers

math.CO2026

Cyclic Neighborhoods in Digraphs

Thilo Hartel, Dieter Rautenbach

Let $D$ be a digraph of order $n$ and size $m$ with the property that no out-neighborhood or in-neighborhood of any vertex is acyclic. We show that, if $D$ is strongly connected, t…

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.CO2025

On the number of maximal independent sets and maximal induced bipartite subgraphs in $K_{4}$ -free graphs

Thilo Hartel, Lucas Picasarri-Arrieta, Dieter Rautenbach

Let $G$ be a $K_{4}$ -free graph of order $n$ and let $k$ be an integer with $0 \leq k \leq n$ . We show the existence of positive constants $η$ and $ν$ such that $G$ has at most $(4-η)^…

math.CO2025

Majority additive coloring and the maximum degree

Christoph Brause, Dieter Rautenbach, Laurin Schwartze

Kamyczura introduced the notion of a majority additive $k$ -coloring of a graph $G$ as a function $c : V (G) \to {1, 2, \dots, k}$ such that $$\left|\left\{u \in N_G(v):\sum_{w \in N_…

math.CO2025

Leaf to leaf path lengths in trees of given degree sequence

Dieter Rautenbach, Johannes Scherer, Florian Werner

For a tree $T$ , let $l p (T)$ be the number of different lengths of leaf to leaf paths in $T$ . For a degree sequence $s$ of a tree, let $rad (s)$ be the minimum radius of a tree…

cs.DS2025

A Faster Algorithm for Independent Cut

Vsevolod Chernyshev, Johannes Rauch, Dieter Rautenbach +1

The previously fastest algorithm for deciding the existence of an independent cut had a runtime of $O^{*} (1.442 3^{n})$ , where $n$ is the order of the input graph. We improve…

math.CO2025

Coloring by Pushing Vertices

Dieter Rautenbach, Laurin Schwartze, Florian Werner

Let $G$ be a graph of order $n$ , maximum degree at most $Δ$ , and no component of order $2$ . Inspired by the famous 1-2-3-conjecture, Bensmail, Marcille, and Orenga define a proper…

cs.DS2025

Cutwidth and Crossings

Johannes Rauch, Dieter Rautenbach

We provide theoretical insights around the cutwidth of a graph and the One-Sided Crossing Minimization (OSCM) problem. OSCM was posed in the Parameterized Algorithms and Computatio…

math.CO2024

An Optimization Approach to Degree Deviation and Spectral Radius

Dieter Rautenbach, Florian Werner

For a finite, simple, and undirected graph $G$ with $n$ vertices and average degree $d$ , Nikiforov introduced the degree deviation of $G$ as $s=\sum_{u\in V(G)}\left|d_G(u)-d\right…

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.CO2024

Degree Deviation and Spectral Radius

Dieter Rautenbach, Florian Werner

For a finite, simple, and undirected graph $G$ with $n$ vertices, $m$ edges, and largest eigenvalue $λ$ , Nikiforov introduced the degree deviation of $G$ as $s=\sum_{u\in V(G)}\lef…

cs.DM2024

Complexity of Deciding the Equality of Matching Numbers

Guilherme C. M. Gomes, Bruno P. Masquio, Paulo E. D. Pinto +4

A matching is said to be disconnected if the saturated vertices induce a disconnected subgraph and induced if the saturated vertices induce a 1-regular graph. The disconnected and…

cs.DS2024

Induced Subforests and Superforests

Dieter Rautenbach, Florian Werner

Graph isomorphism, subgraph isomorphism, and maximum common subgraphs are classical well-investigated objects. Their (parameterized) complexity and efficiently tractable cases have…

cs.DS2024

Largest common subgraph of two forests

Dieter Rautenbach, Florian Werner

A common subgraph of two graphs $G_{1}$ and $G_{2}$ is a graph that is isomorphic to subgraphs of $G_{1}$ and $G_{2}$ . In the largest common subgraph problem the task is to determine a com…

cs.DS2023

On Conflict-Free Cuts: Algorithms and Complexity

Johannes Rauch, Dieter Rautenbach, Uéverton S. Souza

One way to define the Matching Cut problem is: Given a graph $G$ , is there an edge-cut $M$ of $G$ such that $M$ is an independent set in the line graph of $G$ ? We propose the more…

Cyclic Neighborhoods in Digraphs

Degenerate Vertex Cuts in Sparse Graphs

On the number of maximal independent sets and maximal induced bipartite subgraphs in K4​-free graphs

Majority additive coloring and the maximum degree

Leaf to leaf path lengths in trees of given degree sequence

A Faster Algorithm for Independent Cut

Coloring by Pushing Vertices

Cutwidth and Crossings

An Optimization Approach to Degree Deviation and Spectral Radius

Revisiting Extremal Graphs Having No Stable Cutsets

Forest Cuts in Sparse Graphs

Degree Deviation and Spectral Radius

Complexity of Deciding the Equality of Matching Numbers

Induced Subforests and Superforests

Largest common subgraph of two forests

On Conflict-Free Cuts: Algorithms and Complexity

On the number of maximal independent sets and maximal induced bipartite subgraphs in $K_{4}$ -free graphs