Thomas Schweser

dblp:195/6734 · DBLP profile ↗
← Back
3ranked-venue papers
2as first author
1since 2021 · last 2022
0000-0002-4969-7115ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 2 first-author · 1 since 2021
YearPublicationVenuePosition
2022 Digraphs and Variable Degeneracy
abstract
Let $D$ be a digraph, let $p \geq 1$ be an integer, and let $f: V(D) \to \mathbb{N}_0^p$ be a vector function with $f=(f_1,f_2,\ldots,f_p)$. We say that $D$ has an $f$-partition if there is a partition $(V_1,V_2,\ldots,V_p)$ of the vertex set of $D$ such that, for all $i \in [1,p]$, the digraph $D_i=D[V_i]$ is weakly $f_i$-degenerate, that is, in every nonempty subdigraph $D'$ of $D_i$ there is a vertex $v$ such that $\min\{d_{D'}^+(v), d_{D'}^-(v)\} < f_i(v)$. In this paper, we prove that the condition $f_1(v) + f_2(v) + \cdots + f_p(v) \geq \max \{d_D^+(v),d_D^-(v)\}$ for all $v \in V(D)$ is almost sufficient for the existence of an $f$-partition and give a full characterization of the bad pairs $(D,f)$. Among other applications, this leads to a generalization of Brooks' theorem as well as the list-version of Brooks' theorem for digraphs, where a coloring of a digraph is a partition of the digraph into acyclic induced subdigraphs. We furthermore obtain a result bounding the $s$-degenerate chromatic number of a digraph in terms of the maximum of maximum in-degree and maximum out-degree.
Jørgen Bang-Jensen, Thomas Schweser, Michael Stiebitz
SIAM J. Discret. Math.2
2019 Partitions of multigraphs under minimum degree constraints
Thomas Schweser, Michael Stiebitz
Discret. Appl. Math.1
2019 DP-degree colorable hypergraphs
Thomas Schweser
Theor. Comput. Sci.1