Zobrazeno 1 - 10
of 46
pro vyhledávání: '"Mohr, Samuel"'
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 early 1980s, Erd\H{o}s and S\'os initiated the study of the classical Tur\'an problem with a uniformity condition: the uniform Tur\'an density of a hypergraph $H$ is the infimum over all $d$ for which any sufficiently large hypergraph with the
Externí odkaz:
http://arxiv.org/abs/2112.01385
The notion of first order convergence of graphs unifies the notions of convergence for sparse and dense graphs. Ne\v{s}et\v{r}il and Ossona de Mendez [J. Symbolic Logic 84 (2019), 452-472] proved that every first order convergent sequence of graphs f
Externí odkaz:
http://arxiv.org/abs/2103.10354
Publikováno v:
Journal of Graph Algorithms and Applications vol. 25, no. 1, pp. 121-132 (2021)
A $3$-connected graph $G$ is essentially $4$-connected if, for any $3$-cut $S\subseteq V(G)$ of $G$, at most one component of $G-S$ contains at least two vertices. We prove that every essentially $4$-connected maximal planar graph $G$ on $n$ vertices
Externí odkaz:
http://arxiv.org/abs/2101.03802
We prove a conjecture by Garbe et al. [arXiv:2010.07854] by showing that a Latin square is quasirandom if and only if the density of every 2x3 pattern is 1/720+o(1). This result is the best possible in the sense that 2x3 cannot be replaced with 2x2 o
Externí odkaz:
http://arxiv.org/abs/2011.07572
Autor:
Harant, Jochen, Mohr, Samuel
Publikováno v:
Discussiones Mathematicae Graph Theory (2021)
We propose new bounds on the domination number and on the independence number of a graph and show that our bounds compare favorably to recent ones. Our bounds are obtained by using the Bhatia-Davis inequality linking the variance, the expected value,
Externí odkaz:
http://arxiv.org/abs/2008.12601
In the model of randomly perturbed graphs we consider the union of a deterministic graph $\mathcal{G}_\alpha$ with minimum degree $\alpha n$ and the binomial random graph $\mathbb{G}(n,p)$. This model was introduced by Bohman, Frieze, and Martin and
Externí odkaz:
http://arxiv.org/abs/2004.04672
Results on the existence of various types of spanning subgraphs of graphs are milestones in structural graph theory and have been diversified in several directions. In the present paper, we consider "local" versions of such statements. In 1966, for i
Externí odkaz:
http://arxiv.org/abs/2003.04011
Autor:
Mohr, Samuel
A uniquely $k$-colourable graph is a graph with exactly one partition of the vertex set into at most $k$ colour classes. Here, we investigate some constructions of uniquely $k$-colourable graphs and give a construction of $K_k$-free uniquely $k$-colo
Externí odkaz:
http://arxiv.org/abs/2001.08801
Autor:
Fabrici, Igor, Harant, Jochen, Madaras, Tomáš, Mohr, Samuel, Soták, Roman, Zamfirescu, Carol T.
Publikováno v:
Journal of Graph Theory 2020
A graph is $1$-planar if it has a drawing in the plane such that each edge is crossed at most once by another edge. Moreover, if this drawing has the additional property that for each crossing of two edges the end vertices of these edges induce a com
Externí odkaz:
http://arxiv.org/abs/1912.08028