Zobrazeno 1 - 10
of 95
pro vyhledávání: '"Brause, Christoph"'
Given a graph $G$ and sets $\{\alpha_v~|~v \in V(G)\}$ and $\{\beta_v~|~v \in V(G)\}$ of non-negative integers, it is known that the decision problem whether $G$ contains a spanning tree $T$ such that $\alpha_v \le d_T (v) \le \beta_v $ for all $v \i
Externí odkaz:
http://arxiv.org/abs/2210.04669
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 loose edge-connection of graphs. A connected edge-coloured graph $G$ i
Externí odkaz:
http://arxiv.org/abs/2206.11604
Publikováno v:
In Discrete Applied Mathematics 31 December 2024 359:34-44
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 not contain some graph $H$ as an induced subgraph, have proven to be an
Externí odkaz:
http://arxiv.org/abs/2105.04588
Autor:
Brause, Christoph, Golovach, Petr, Martin, Barnaby, Ochem, Pascal, Paulusma, Daniël, Smith, Siani
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 forest, star forest or disjoint union of vertices and edges, respectively
Externí odkaz:
http://arxiv.org/abs/2104.10593
Autor:
Brause, Christoph, Doan, Trung Duy, Holub, Přemysl, Kabela, Adam, Ryjáček, Zdeněk, Schiermeyer, Ingo, Vrána, Petr
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 that all graphs in the class are perfect if and only if $X$ is an ind
Externí odkaz:
http://arxiv.org/abs/2102.08783
Given a set $\mathcal{H}$ of graphs, let $f_\mathcal{H}^\star\colon \mathbb{N}_{>0}\to \mathbb{N}_{>0}$ be the optimal $\chi$-binding function of the class of $\mathcal{H}$-free graphs, that is, $$f_\mathcal{H}^\star(\omega)=\max\{\chi(G): G\text{ is
Externí odkaz:
http://arxiv.org/abs/2005.02250
Autor:
Brause, Christoph, Holub, Přemysl, Kabela, Adam, Ryjáček, Zdeněk, Schiermeyer, Ingo, Vrána, Petr
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\omega$-colourable where $\omega$ denotes the clique number of $G$. We study $(K_{1,3}, Y)$-f
Externí odkaz:
http://arxiv.org/abs/1903.09403
Publikováno v:
In Discrete Applied Mathematics 30 October 2022 320:211-222
Publikováno v:
In Theoretical Computer Science 21 September 2022 930:37-52