Zobrazeno 1 - 10
of 99
pro vyhledávání: '"Winfried Hochstättler"'
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol vol. 24, no. 1, Iss Graph Theory (2022)
We study the neighborhood polynomial and the complexity of its computation for chordal graphs. The neighborhood polynomial of a graph is the generating function of subsets of its vertices that have a common neighbor. We introduce a parameter for chor
Externí odkaz:
https://doaj.org/article/436f6d72739d4a389ef6add764aae26f
Publikováno v:
AKCE International Journal of Graphs and Combinatorics, Vol 17, Iss 3, Pp 992-994 (2020)
Reed (1987) showed that, if two graphs are P4-isomorphic, then either both are perfect or none of them is. In this note, we will derive an analogous result for perfect digraphs.
Externí odkaz:
https://doaj.org/article/4e24ce3cca934cb78686094340005656
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol vol. 22 no. 1, Iss Graph Theory (2020)
It has been shown by Bokal et al. that deciding 2-colourability of digraphs is an NP-complete problem. This result was later on extended by Feder et al. to prove that deciding whether a digraph has a circular $p$-colouring is NP-complete for all rati
Externí odkaz:
https://doaj.org/article/a58f1877efb441d49adc86790282ae01
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol Vol. 18 no. 1, Iss Graph Theory (2015)
We prove that the game colouring number of the $m$-th power of a forest of maximum degree $\Delta\ge3$ is bounded from above by \[\frac{(\Delta-1)^m-1}{\Delta-2}+2^m+1,\] which improves the best known bound by an asymptotic factor of 2.
Externí odkaz:
https://doaj.org/article/6e74754d2d6843daad44601d5dbd0f4d
Publikováno v:
Discrete Applied Mathematics. 320:81-94
For a fixed simple digraph $F$ and a given simple digraph $D$, an $F$-free $k$-coloring of $D$ is a vertex-coloring in which no induced copy of $F$ in $D$ is monochromatic. We study the complexity of deciding for fixed $F$ and $k$ whether a given sim
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e3232f9b746ccfac2dc4f5adeef9261a
https://doi.org/10.1016/j.dam.2022.05.015
https://doi.org/10.1016/j.dam.2022.05.015
Publikováno v:
AKCE International Journal of Graphs and Combinatorics, Vol 17, Iss 3, Pp 992-994 (2020)
Reed showed that, if two graphs are $P_4$-isomorphic, then either both are perfect or none of them is. In this note we will derive an analogous result for perfect digraphs.
5 pages, 1 figure
5 pages, 1 figure
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::412a907d6fc5663311211f4c82deb029
https://doi.org/10.1016/j.akcej.2019.12.018
https://doi.org/10.1016/j.akcej.2019.12.018
Autor:
Winfried Hochstättler, Volkmar Welker
Publikováno v:
Mathematische Zeitschrift. 293:1415-1430
We generalize the Varchenko matrix of a hyperplane arrangement to oriented matroids. We show that the celebrated determinant formula for the Varchenko matrix, first proved by Varchenko, generalizes to oriented matroids. It follows that the determinan
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6741159b368719ae20cb898437798c7e
https://doi.org/10.1007/s00209-019-02275-z
https://doi.org/10.1007/s00209-019-02275-z
Autor:
Georg Still, Daniël Paulusma, Bodo Manthey, Winfried Hochstättler, Johann L. Hurink, Britta Peis
Publikováno v:
Discrete applied mathematics. 303:2-3
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5985fd5a3a134254ee475324f8866a1e
https://doi.org/10.1016/j.dam.2021.08.034
https://doi.org/10.1016/j.dam.2021.08.034
Autor:
Winfried Hochstättler, Johanna Wiehe
Publikováno v:
Trends in Mathematics ISBN: 9783030838225
We define a trivariate polynomial combining the NL-coflow and the NL-flow polynomial, which build a dual pair counting acyclic colorings of directed graphs, in the more general setting of regular oriented matroids.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8d2d2792578d28104bb311dd4f36a1a9
https://doi.org/10.1007/978-3-030-83823-2_59
https://doi.org/10.1007/978-3-030-83823-2_59
Autor:
Johanna Wiehe, Winfried Hochstättler
Publikováno v:
AIRO Springer Series ISBN: 9783030630713
An acyclic coloring of a digraph as defined by V. Neumann-Lara is a vertex-coloring such that no monochromatic directed cycles occur. Counting the number of such colorings with k colors can be done by counting so-called Neumann-Lara-coflows (NL-coflo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::075ac770b39c4b3d63a2abc52ae79b55
https://doi.org/10.1007/978-3-030-63072-0_1
https://doi.org/10.1007/978-3-030-63072-0_1