Christoph Brause

activity

20152025

most citedA characterization of trees with equal 2-domination and 2-independence numbers

3 citations · 7 across the 12 of their papers we have counts for

collaborators

12 papers

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

On the distinguishing chromatic number in hereditary graph classes

Christoph Brause, Rafał Kalinowski, Monika Pilśniak +1

The distinguishing chromatic number of a graph $G$ , denoted $χ_{D} (G)$ , is the minimum number of colours in a proper vertex colouring of $G$ that is preserved by the identity automor…

math.CO2022

Minimum Spanning Trees with Bounded Degrees of Vertices in a Specified Stable Set

Christoph Brause, Jochen Harant, Florian Hörsch +1

Given a graph $G$ and sets ${α_{v} ∣ v \in V (G)}$ and ${β_{v} ∣ v \in V (G)}$ of non-negative integers, it is known that the decision problem whether $G$ contains a spanning tree $T…

math.CO2022

Loose edge-connection of graphs

Christoph Brause, Stanislav Jendrol, Ingo Schiermeyer

In the last years, connection concepts such as rainbow connection and proper connection appeared in graph theory and obtained a lot of attention. In this paper, we investigate the…

cs.DS2021★ 3 cited

Partitioning H-Free Graphs of Bounded Diameter

Christoph Brause, Petr Golovach, Barnaby Martin +2

A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of $H$ -free graphs, that is, graphs that do n…

cs.DS2021

Acyclic, Star, and Injective Colouring: Bounding the Diameter

Christoph Brause, Petr Golovach, Barnaby Martin +3

We examine the effect of bounding the diameter for well-studied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a for…

math.CO2021

Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4

Christoph Brause, Trung Duy Doan, Přemysl Holub +4

For every graph $X$ , we consider the class of all connected ${K_{1, 3}, X}$ -free graphs which are distinct from an odd cycle and have independence number at least $4$ , and we show…

math.CO2020★ 1 cited

Homogeneous sets, clique-separators, critical graphs, and optimal $χ$ -binding functions

Christoph Brause, Maximilian Geißer, Ingo Schiermeyer

Given a set $H$ of graphs, let $f_{H}^{⋆} : N_{> 0} \to N_{> 0}$ be the optimal $χ$ -binding function of the class of $H$ -free graph…

math.CO2019

On forbidden induced subgraphs for K_{1,3}-free perfect graphs

Christoph Brause, Přemysl Holub, Adam Kabela +3

Considering connected $K_{1, 3}$ -free graphs with independence number at least $3$ , Chudnovsky and Seymour (2010) showed that every such graph, say $G$ , is $2 ω$ -colourable where $ω$ …

math.CO2018

On the extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives

S. Ehard, D. Rautenbach

The famous lower bound $α (G) \geq \sum_{u \in V (G)} \frac{1}{d _{G} ( u ) + 1}$ on the independence number $α (G)$ of a graph $G$ due to Caro and Wei is known to be tight if and only if the co…

math.CO2016★ 3 cited

A characterization of trees with equal 2-domination and 2-independence numbers

Christoph Brause, Michael A. Henning, Marcin Krzywkowski

A set $S$ of vertices in a graph $G$ is a $2$ -dominating set if every vertex of $G$ not in $S$ is adjacent to at least two vertices in $S$ , and $S$ is a $2$ -independent set if ever…

math.CO2015

Local Connectivity, Local Degree Conditions, some Forbidden Induced Subgraphs, and Cycle Extendability

Christoph Brause, Dieter Rautenbach, Ingo Schiermeyer

The research in the present paper was motivated by the conjecture of Ryjáček that every locally connected graph is weakly pancyclic. For a connected locally connected graph $G$ of…