Dieter Rautenbach

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 common subgraph for two given graphs $G_1$ and $G_2$ that is of maximum possible size ${\rm lcs}(G_1,G_2)$. This natural problem generalizes the well-studied graph isomorphism problem, has many applications, and remains NP-hard even restricted to unions of paths. We present a simple $4$-approximation algorithm for forests, and, for every fixed $\epsilon\in (0,1)$, we show that, for two given forests $F_1$ and $F_2$ of order at most $n$, one can determine in polynomial time a common subgraph $F$ of $F_1$ and $F_2$ with at least ${\rm lcs}(F_1,F_2)-\epsilon n$ edges. Restricted to instances with ${\rm lcs}(F_1,F_2)\geq cn$ for some fixed positive $c$, this yields a polynomial time approximation scheme. Our approach relies on the approximation of the given forests by structurally simpler forests that are composed of copies of only $O(\log (n))$ different starlike rooted trees and iterative quantizations of the options for the solutions.

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-η)^{(5-η)k-n}(5-η)^{n-(4-η)k}$ maximal independent sets of order $k$ and at most $O\left((12-ν)^{\frac{n}{4}}\right)$ maximal induced bipartite subgraphs.

Kamyczura introduced the notion of a majority additive $k$-coloring of a graph $G$ as a function $c: V(G) \to \{1,2,\ldots,k\}$ such that $$\left|\left\{u \in N_G(v):\sum_{w \in N_G(u)} c(w) = s \right\}\right|\leq \max\left\{1,\frac{d_G(v)}{2}\right\}$$ for every vertex $v$ of $G$ and every positive integer $s$. We show that every graph $G$ of maximum degree $Δ$ admitting a majority additive coloring has a majority additive $\mathcal{O}\left(Δ^2\right)$-coloring. Under additional restrictions we improve this to sublinear in $Δ$. We show that determining whether a majority additive $k$-coloring exists for a given graph is NP-complete for all $k\geq 2$.

The previously fastest algorithm for deciding the existence of an independent cut had a runtime of $\mathcal{O}^*(1.4423^n)$, where $n$ is the order of the input graph. We improve this to $\mathcal{O}^*(1.4143^n)$. In fact, we prove a runtime of $\mathcal{O}^*\left( 2^{(\frac{1}{2}-α_Δ)n} \right)$ on graphs of order $n$ and maximum degree at most $Δ$, where $α_Δ=\frac{1}{2+4\lfloor \fracΔ{2} \rfloor}$. Furthermore, we show that the problem is fixed-parameter tractable on graphs of order $n$ and minimum degree at least $βn$ for some $β> \frac{1}{2}$, where $β$ is the parameter.

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 pushing scheme of $G$ as a function $ρ:V(G)\to\mathbb{N}_0$ for which $$σ:V(G)\to\mathbb{N}_0:u\mapsto \left(1+ρ(u)\right)d_G(u)+\sum_{v\in N_G(u)}ρ(v)$$ is a vertex coloring, that is, adjacent vertices receive different values under $σ$. They show the existence of a proper pushing scheme $ρ$ with $\max\{ ρ(u):u\in V(G)\}\leq Δ^2$ and conjecture that this upper bound can be improved to $Δ$. We show their conjecture for cubic graphs and regular bipartite graphs. Furthermore, we show the existence of a proper pushing scheme $ρ$ with $\sum_{u\in V(G)}ρ(u)\leq \left(2Δ^2+Δ\right)n/6$.

We show that every graph $G$ of maximum degree $\Delta$ and sufficiently large order has a vertex cutset $S$ of order at most $\Delta$ that induces a subgraph $G[S]$ of maximum degree at most $\Delta-3$. For $\Delta\in \{ 4,5\}$, we refine this result by considering also the average degree of $G[S]$. If $G$ has no $K_{r,r}$ subgraph, then we show the existence of a vertex cutset that induces a subgraph of maximum degree at most $\Big(1-\frac{1}{{r\choose 2}}\Big)\Delta+O(1)$.

For a finite, simple, and undirected graph $G$ with $n$ vertices, $m$ edges, and largest eigenvalue $\lambda$, Nikiforov introduced the degree deviation of $G$ as$$s=\sum_{u\in V(G)}\left|d_G(u)-\frac{2m}{n}\right|.$$Contributing to a conjecture of Nikiforov, we show $\lambda-\frac{2m}{n}\leq \sqrt{\frac{2s}{3}}$. For our result, we show that the largest eigenvalue of a graph that arises from a bipartite graph with $m_{A,B}$ edges by adding $m_A$ edges within one of the two partite sets is at most $$\sqrt{m_A+m_{A,B}+\sqrt{m_A^2+2m_Am_{A,B}}},$$which is a common generalization of results due to Stanley and Bhattacharya, Friedland, and Peled.

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 Computational Experiments Challenge 2024, where the cutwidth of the input graph was the parameter in the parameterized track. We prove an asymptotically sharp upper bound on the size of a graph in terms of its order and cutwidth. As the number of so-called unsuited pairs is one of the factors that determine the difficulty of an OSCM instance, we provide a sharp upper bound on them in terms of the order $n$ and the cutwidth of the input graph. If the cutwidth is bounded by a constant, this implies an $\mathcal{O}(2^n)$-time algorithm, while the trivial algorithm has a running time of $\mathcal{O}(2^{n^2})$. At last, we prove structural properties of the so-called crossing numbers in an OSCM instance.

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|$. Provided that $G$ has largest eigenvalue $λ$, minimum degree at least $δ$, and maximum degree at most $Δ$, where $0\leqδ<d<Δ \frac{dn}{\sqrt{2}}. \end{cases}$$ Our results are based on a smoothing technique relating the degree deviation and the largest eigenvalue to low-dimensional non-linear optimization problems.