10 citations · 20 across the 11 of their papers we have counts for
15 papers · 1 filter
Minimum Spanning Trees with Bounded Degrees of Vertices in a Specified Stable Set
Christoph Brause, Jochen Harant, Florian Hörsch +1
Given a graph and sets and of non-negative integers, it is known that the decision problem whether contains a spanning tree $T…
Uniform Turán density of cycles
Matija Bucić, Jacob W. Cooper, Daniel Kráľ +2
In the early 1980s, Erdős and Sós initiated the study of the classical Turán problem with a uniformity condition: the uniform Turán density of a hypergraph is the infimum over…
Strong modeling limits of graphs with bounded tree-width
Andrzej Grzesik, Daniel Kráľ, Samuel Mohr
The notion of first order convergence of graphs unifies the notions of convergence for sparse and dense graphs. Nešetřil and Ossona de Mendez [J. Symbolic Logic 84 (2019), 452-472]…
Circumference of essentially 4-connected planar triangulations
Igor Fabrici, Jochen Harant, Samuel Mohr +1
A -connected graph is essentially -connected if, for any -cut of , at most one component of contains at least two vertices. We prove that ev…
Quasirandom Latin squares
Jacob W. Cooper, Daniel Kral, Ander Lamaison +1
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…
New bounds on domination and independence in graphs
Jochen Harant, Samuel Mohr
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…
Random perturbation of sparse graphs
Max Hahn-Klimroth, Giulia S. Maesaka, Yannick Mogge +2
In the model of randomly perturbed graphs we consider the union of a deterministic graph with minimum degree and the binomial random graph . T…
Rooted Minors and Locally Spanning Subgraphs
Thomas Böhme, Jochen Harant, Matthias Kriesell +2
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…
A Construction of Uniquely Colourable Graphs with Equal Colour Class Sizes
Samuel Mohr
A uniquely -colourable graph is a graph with exactly one partition of the vertex set into at most colour classes. Here, we investigate some constructions of uniquely -col…
Long Cycles and Spanning Subgraphs of Locally Maximal 1-planar Graphs
Igor Fabrici, Jochen Harant, Tomáš Madaras +3
A graph is -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 e…
Kempe Chains and Rooted Minors
Matthias Kriesell, Samuel Mohr
A (minimal) transversal of a partition is a set which contains exactly one element from each member of the partition and nothing else. A coloring of a graph is a partition of its v…
On the Circumference of Essentially 4-connected Planar Graphs
Igor Fabrici, Jochen Harant, Samuel Mohr +1
A planar graph is essentially -connected if it is 3-connected and every of its 3-separators is the neighborhood of a single vertex. Jackson and Wormald proved that every essenti…
Rooted complete minors in line graphs with a Kempe coloring
Matthias Kriesell, Samuel Mohr
It has been conjectured that if a finite graph has a vertex coloring such that the union of any two color classes induces a connected graph, then for every set of vertices cont…
Longer Cycles in Essentially 4-Connected Planar Graphs
Igor Fabrici, Jochen Harant, Samuel Mohr +1
A planar 3-connected graph is called \emph{essentially -connected} if, for every 3-separator , at least one of the two components of is an isolated vertex. Jackson…
On Selkow's Bound on the Independence Number of Graphs
Jochen Harant, Samuel Mohr
For a graph with vertex set and independence number , S. M. Selkow (Discrete Mathematics, 132(1994)363--365) established the famous lower bound $\sum\limits_{v\in…