Publications

Here is list of my publications. Please click on them to unfold the abstract. The complete list can also be downloaded as pdf.

Preprints

16. Christoph Brause, Jochen Harant, Florian Hörsch, and Samuel Mohr:
    Spanning trees of smallest maximum degree in subdivisions of graphs
    arXiv: 2210.04669. bibTeX: download.

    Abstract: Given a graph \(G\) and a positive integer \(k\), we study the question whether \(G^\star \) has a spanning tree of maximum degree at most \(k\) where \(G^\star \) is the graph that is obtained from \(G\) by subdividing every edge once. Using matroid intersection, we obtain a polynomial algorithm for this problem and a characterization of its positive instances. We use this characterization to show that \(G^\star \) has a spanning tree of bounded maximum degree if \(G\) is contained in some particular graph class. We study the class of 3-connected graphs which are embeddable in a fixed surface and the class of \((p-1)\)-connected \(K_p\)-minor-free graphs for a fixed integer \(p\). We also give tightness examples for most of these classes.

17. Andrzej Grzesik, Daniel Kráľ, and Samuel Mohr:
    Strong modeling limits of graphs with bounded tree-width
    arXiv: 2103.10354. bibTeX: download.

    Abstract: 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] proved that every first order convergent sequence of graphs from a nowhere-dense class of graphs has a modeling limit and conjectured the existence of such modeling limits with an additional property, the strong finitary mass transport principle. The existence of modeling limits satisfying the strong finitary mass transport principle was proved for first order convergent sequences of trees by Nešetřil and Ossona de Mendez [Electron. J. Combin. 23 (2016), P2.52] and for first order sequences of graphs with bounded path-width by Gajarský et al. [Random Structures Algorithms 50 (2017), 612–635]. We establish the existence of modeling limits satisfying the strong finitary mass transport principle for first order convergent sequences of graphs with bounded tree-width.

18. Thomas Böhme, Jochen Harant, Matthias Kriesell, Samuel Mohr, and Jens M Schmidt:
    Rooted Minors and Locally Spanning Subgraphs
    arXiv: 2003.04011. bibTeX: download.

    Abstract: Given a finite, undirected, and simple graph \(G\) and \(X\subseteq V(G)\), let \(\mathcal {M}\) be a partition of a subset of \(V(G)\) into connected sets — called bags — such that each bag contains at most one vertex of \(X\) and \(X\) is a subset of the union of all bags. If \(M\) is a simple graph on the vertex set \(\mathcal {M}\) such that there is an edge of \(G\) connecting two bags of \(\mathcal {M}\) if these two bags are adjacent in \(M\), then \(M\) is an minor of \(G\) rooted at \(X\). We consider the problem whether \(G\) has a highly connected minor rooted at \(X\) if \(X\) cannot be separated in \(G\) by removing a few vertices of \(G\).
    As an application of the achieved results, statements on locally spanning subgraphs of \(G\), i. e. subgraphs containing \(X\), are presented.

19. Matthias Kriesell and Samuel Mohr:
    Kempe chains and rooted minors
    arXiv: 1911.09998. bibTeX: download.

    Abstract: A 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 vertex set into anti-cliques, that is, sets of pairwise non-adjacent vertices. We study the following problem: Given a transversal \(T\) of a proper coloring \(\mathcal {C}\) of some graph \(G\), is there a partition \(\mathcal {H}\) of a subset of \(V(G)\) into connected sets such that \(T\) is a transversal of \(\mathcal {H}\) and such that two sets of \(\mathcal {H}\) are adjacent if their corresponding vertices from \(T\) are connected by a path in \(G\) using only two colors?
    It has been suggested by the first author to study the following question: for any transversal \(T\) of a coloring \(\mathcal {C}\) of order \(k\) of some graph \(G\) such that any pair of color classes induces a connected graph, does there exist such a partition \(\mathcal {H}\) with pairwise adjacent sets (which would prove Hadwiger’s Conjecture for the class of uniquely optimally colorable graphs)? This is open for small \(k \geq 5\), here we give a proof for the case that \(k=5\) and the subgraph induced by \(T\) is connected. Moreover, we show that for \(k\geq 7\), it is not sufficient for the existence of \(\mathcal {H}\) as above just to force any two transversal vertices to be connected by a 2-colored path.

Journal Publications

1. Matija Bucić, Jacob W Cooper, Daniel Kráľ, Samuel Mohr, and David Correia Munhá:
   Uniform Turán density of cycles
   Transactions of the American Mathematical Society (2023). to appear. doi: 10.1090/tran/8873. arXiv: 2112.01385. bibTeX: download.

   Abstract: 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 \(H\) is the infimum over all \(d\) for which any sufficiently large hypergraph with the property that all its linear-size subhyperghraphs have density at least \(d\) contains \(H\). In particular, they raise the questions of determining the uniform Turán densities of \(K_4^{(3)-}\) and \(K_4^{(3)}\). The former question was solved only recently in [Israel J. Math. 211 (2016), 349–366] and [J. Eur. Math. Soc. 20 (2018), 1139–1159], while the latter still remains open for almost 40 years. In addition to \(K_4^{(3)-}\), the only 3-uniform hypergraphs whose uniform Turán density is known are those with zero uniform Turán density classified by Reiher, Rödl and Schacht [J. London Math. Soc. 97 (2018), 77–97] and a specific family with uniform Turán density equal to \(1/27\). We develop new tools for embedding hypergraphs in host hypergraphs with positive uniform density and apply them to completely determine the uniform Turán density of a fundamental family of \(3\)-uniform hypergraphs, namely tight cycles \(C_\ell ^{(3)}\). The uniform Turán density of \(C_\ell ^{(3)}\), \(\ell \ge 5\), is equal to \(4/27\) if \(\ell \) is not divisible by three, and is equal to zero otherwise. The case \(\ell =5\) resolves a problem suggested by Reiher.

2. Jochen Harant and Samuel Mohr:
   New bounds on domination and independence in graphs
   Discussiones Mathematicae Graph Theory 43.3 (2023), pp. 809–824. doi: 10.7151/dmgt.2406. arXiv: 2008.12601. bibTeX: download.

   Abstract: 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, the minimum, and the maximum of a random variable with bounded distribution.

3. Jacob W Cooper, Daniel Kráľ, Ander Lamaison, and Samuel Mohr:
   Quasirandom Latin squares
   Random Structures and Algorithms 61.2 (2022), pp. 298–308. doi: 10.1002/rsa.21060. arXiv: 2011.07572. bibTeX: download.

   Abstract: 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 \(2\times 3\) pattern is \(1/720+o(1)\). This result is the best possible in the sense that \(2\times 3\) cannot be replaced with \(2\times 2\) or \(1\times n\) for any \(n\).

4. Max Hahn-Klimroth, Giulia S. Maesaka, Yannick Mogge, Samuel Mohr, and Olaf Parczyk:
   Random perturbation of sparse graphs
   Electronic Journal of Combinatorics 28.2 (2021), P2.26. doi: 10.37236/9510. arXiv: 2004.04672. bibTeX: download.

   Abstract: 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 for Hamilton cycles their result bridges the gap between Dirac’s theorem and the results by Pósa and Korshunov on the threshold in \(\mathbb {G}(n,p)\). In this note we extend this result in \(\mathcal {G}_\alpha \cup \mathbb {G}(n,p)\) to sparser graphs with \(\alpha =o(1)\). More precisely, for any \(\varepsilon >0\) and \(\alpha \colon \mathbb {N} \mapsto (0,1)\) we show that a.a.s. \(\mathcal {G}_\alpha \cup \mathbb {G}(n,\beta /n)\) is Hamiltonian, where \(\beta = -(6 + \varepsilon ) \log (\alpha )\). If \(\alpha >0\) is a fixed constant this gives the aforementioned result by Bohman, Frieze, and Martin and if \(\alpha =O(1/n)\) the random part \(\mathbb {G}(n,p)\) is sufficient for a Hamilton cycle. We also discuss embeddings of bounded degree trees and other spanning structures in this model, which lead to interesting questions on almost spanning embeddings into \(\mathbb {G}(n,p)\).

5. Igor Fabrici, Jochen Harant, Samuel Mohr, and Jens M Schmidt:
   Circumference of essentially 4-connected planar triangulations
   Journal of Graph Algorithms and Applications 25.1 (2021), pp. 121–132. doi: 10.7155/jgaa.00552. arXiv: 2101.03802. bibTeX: download.

   Abstract: 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 contains a cycle of length at least \(\frac {2}{3}(n+4)\); moreover, this bound is sharp.

6. Samuel Mohr:
   A construction of uniquely colourable graphs with equal colour class sizes
   Discrete Applied Mathematics 303 (2021), pp. 122–126. doi: 10.1016/j.dam.2020.11.015. arXiv: 2001.08801. bibTeX: download.

   Abstract: A uniquely \(k\)-colourable graph is a graph with exactly one partition of the vertex set into \(k\) colour classes. Here, we investigate some constructions of uniquely \(k\)-colourable graphs and give a construction of \(K_k\)-free uniquely \(k\)-colourable graphs with equal colour class sizes.

7. Igor Fabrici, Jochen Harant, Tomáš Madaras, Samuel Mohr, Roman Soták, and Carol T Zamfirescu:
   Long cycles and spanning subgraphs of locally maximal 1-planar graphs
   Journal of Graph Theory 95.1 (2020), pp. 125–137. doi: 10.1002/jgt.22542. arXiv: 1912.08028. bibTeX: download.

   Abstract: Chen and Yu verified a conjecture of Moon and Moser that there is a positive constant \(c\) such that the length of a longest cycle of each 3-connected planar graph \(G\) is at least \(c\cdot |V(G)|^{\log _32}\).
   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 and it is maximal 1-planar if it is 1-planar and no edge between non-adjacent vertices can be added to keep its 1-planarity. We will confirm the results of Moon and Moser and Chen and Yu for the class of maximal 1-planar that a longest cycle of 3-connected maximal 1-planar is at least \(c\cdot |V(G)|^{\log _32}\) and this bound is asymptotically optimal.

8. Igor Fabrici, Jochen Harant, Samuel Mohr, and Jens M Schmidt:
   On the circumference of essentially 4-connected planar graphs
   Journal of Graph Algorithms and Applications 24.1 (2020), pp. 21–46. doi: 10.7155/jgaa.00516. arXiv: 1806.09413. bibTeX: download.

   Abstract: A planar graph is essentially \(4\)-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 essentially 4-connected planar graph \(G\) on \(n\) vertices contains a cycle of length at least \(\frac {2n+4}{5}\), and this result has recently been improved multiple times. In this paper, we prove that every essentially 4-connected planar graph \(G\) on \(n\) vertices contains a cycle of length at least \(\frac {5}{8}(n+2)\). This improves the previously best-known lower bound \(\frac {3}{5}(n+2)\).

9. Igor Fabrici, Jochen Harant, Samuel Mohr, and Jens M Schmidt:
   Longer cycles in essentially 4-connected planar graphs
   Discussiones Mathematicae Graph Theory 40.1 (2020), pp. 269–277. doi: 10.7151/dmgt.2133. arXiv: 1710.05619. bibTeX: download.

   Abstract: A planar 3-connected graph \(G\) is called essentially \(4\)-connected if, for every 3-separator \(S\), at least one of the two components of \(G-S\) is an isolated vertex. Jackson and Wormald proved that the length \(\mathrm {circ}(G)\) of a longest cycle of any essentially 4-connected planar graph \(G\) on \(n\) vertices is at least \(\frac {2n+4}{5}\) and Fabrici, Harant and Jendroľ improved this result to \(\mathrm {circ}(G)\geq \frac {1}{2}(n+4)\). In the present paper, we prove that an essentially 4-connected planar graph on \(n\) vertices contains a cycle of length at least \(\frac {3}{5}(n+2)\) and that such a cycle can be found in time \(O(n^2)\).

10. Matthias Kriesell and Samuel Mohr:
    Rooted complete minors in line graphs with a Kempe coloring
    Graphs and Combinatorics 35.2 (2019), pp. 551–557. doi: 10.1007/s00373-019-02012-7. arXiv: 1804.06641. bibTeX: download.

    Abstract: 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 \(T\) of vertices containing exactly one member from each color class there exists a complete minor such that \(T\) contains exactly one member from each branching set. Here we prove the statement for line graphs.

11. Jochen Harant and Samuel Mohr:
    On Selkow’s bound on the independence number of graphs
    Discussiones Mathematicae Graph Theory 39.3 (2019), pp. 655–657. doi: 10.7151/dmgt.2100. arXiv: 1705.03779. bibTeX: download.

    Abstract: For a graph \(G\) with vertex set \(V(G)\) and independence number \(\alpha (G)\), S. M. Selkow (Discrete Mathematics, 132(1994)363–365) established the famous lower bound \(\sum \limits _{v\in V(G)}\frac {1}{d(v)+1}(1+\max \{\frac {d(v)}{d(v)+1}-\sum \limits _{u\in N(v)}\frac {1}{d(u)+1},0 \})\) on \(\alpha (G)\), where \(N(v)\) and \(d(v)=|N(v)|\) denote the neighborhood and the degree of a vertex \(v\in V(G)\), respectively. However, Selkow’s original proof of this result is incorrect. We give a new probabilistic proof of Selkow’s bound here.

12. Jochen Harant and Samuel Mohr:
    Maximum weighted induced subgraphs
    Discrete Mathematics 339.7 (2016), pp. 1954–1959. doi: 10.1016/j.disc.2015.07.013. bibTeX: download.

    Abstract: Let \(G\) be a finite, simple, undirected graph with vertex set \(V(G)\) and \(\mathcal {F}\) be a family of graphs. A subgraph of \(G\) is \(\mathcal {F}\)-free if it does not contain any graph of \(\mathcal {F}\) as induced subgraph. In this paper, we present lower bounds on the maximum weight \(w(H) = \sum _{i\in V(H)} w_i\) of an \(\mathcal {F}\)-free induced subgraph \(H\) of \(G\), where \(w_i > 0\) denotes the weight of a vertex \(i\in V(G)\).

Refereed Conference Proceedings

1. Samuel Mohr:
   Rooted Structures in Graphs
   Proceedings of the 3rd BYMAT Conference Vol. 2 (2021), pp. 95–98. bibTeX: download.
   url: https://temat.es/monograficos/issue/view/vol-2.

   Abstract: A transversal of a partition is a set which contains exactly one element from each member of the partition and nothing else. A colouring of a graph is a partition of its vertex set into anticliques, that is, sets of pairwise nonadjacent vertices. We study the following problem: Given a transversal \(T\) of a proper colouring \(\mathcal {C}\) of some graph \(G\), is there a partition \(\mathfrak {H}\) of a subset of \(V(G)\) into connected sets such that \(T\) is a transversal of \(\mathfrak {H}\) and any two distinct sets of \(\mathfrak {H}\) are adjacent?
   It has been conjectured by Matthias Kriesell [Journal of Graph Theory 85.1 (2017), pp. 207–216] that for any transversal \(T\) of a colouring \(\mathcal {C}\) of order \(k\) of some graph \(G\) such that any pair of colour classes induces a connected subgraph, there exists such a partition \(\mathfrak {H}\) with pairwise adjacent sets. This would prove Hadwiger’s conjecture for the class of uniquely optimally colourable graphs; however it is open for each \(k \geq 5\).
   This paper will provide an overview about the stated conjecture. It extracts associated results from my PhD thesis and the related papers, summarises their relevance to the stated problem, and discusses some unsuccessful attempts.

2. Andrzej Grzesik, Daniel Kráľ, and Samuel Mohr:
   Strong modeling limits of graphs with bounded tree-width
   Extended Abstracts EuroComb 2021. Trends in Mathematics 14 (2021). Eurocomb 2021. doi: 10.1007/978-3-030-83823-2_43. bibTeX: download.

   Abstract: 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] proved that every first order convergent sequence of graphs from a nowhere-dense class of graphs has a modeling limit and conjectured the existence of such modeling limits with an additional property, the strong finitary mass transport principle. The existence of modeling limits satisfying the strong finitary mass transport principle was proved for first order convergent sequences of trees by Nešetřil and Ossona de Mendez [Electron. J. Combin. 23 (2016), P2.52] and for first order sequences of graphs with bounded path-width by Gajarský et al. [Random Structures Algorithms 50 (2017), 612–635]. We establish the existence of modeling limits satisfying the strong finitary mass transport principle for first order convergent sequences of graphs with bounded tree-width.

3. Samuel Mohr:
   On the circumference of 3-connected maximal 1-planar graphs
   Bordeaux Graph Workshop 2019, pp. 222–223. bibTeX: download.
   url: http://bgw.labri.fr/2019/booklet.pdf.

   Abstract: Chen and Yu verified a conjecture of Moon and Moser that there is a positive constant \(c\) such that the length of a longest cycle of each 3-connected planar graph \(G\) is at least \(c\cdot |V(G)|^{\log _32}\).
   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 and it is maximal 1-planar if it is 1-planar and no edge between non-adjacent vertices can be added to keep its 1-planarity. We will confirm the results of Moon and Moser and Chen and Yu for the class of maximal 1-planar that a longest cycle of 3-connected maximal 1-planar is at least \(c\cdot |V(G)|^{\log _32}\) and this bound is asymptotically optimal.

4. Samuel Mohr:
   Cycles through a set of specified vertices of a planar graph
   Acta Mathematica Universitatis Comenianae 88.3 (2019). Eurocomb 2019, pp. 963–966. bibTeX: download.
   url: http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1286.

   Abstract: Confirming a conjecture of Plummer, Thomas and Yu proved that a 4-connected planar graph contains a cycle through all but two (freely choosable) vertices. Here we prove that a planar graph \(G\) contains a cycle through \(X\setminus \{x_1,x_2\}\) if \(X\subseteq V(G)\), \(X\) large enough, \(x_1,x_2\in X\), and \(X\) cannot be separated in \(G\) by removing less than 4 vertices.

5. Samuel Mohr:
   On uniquely colourable graphs
   Cologne-Twente Workshop 2019, pp. 103–105. bibTeX: download.
   url: http://wwwhome.math.utwente.nl/~ctw/CTW2019ProceedingsFinal.pdf.

   Abstract: A uniquely \(k\)-colourable graph is a graph with exactly one partition of the vertex set into \(k\) colour classes. Here, we investigate some constructions of uniquely \(k\)-colourable graphs and give a construction of \(K_k\)-free uniquely \(k\)-colourable graphs with equal colour class sizes.

Minor Research Contributions

During an Erasmus exchange stay at Vienna University of Technology for six months in 2015, I worked on a joint project titled “Operator theory in indefinite inner product space” with the “Research Group for Functional Analysis” of Professor Harald Woracek; results can be found in:

1. Henk de Snoo and Harald Woracek:
   Compressed resolvents, \(Q\)-functions and \(h_0\)-resolvents in almost pontryagin spaces
   Indefinite Inner Product Spaces, Schur Analysis, and Differential Equations. Springer, 2018, pp. 425–484. doi: 10.1007/978-3-319-68849-7_18. bibTeX: download.

   Abstract: The interest of this paper lies in the selfadjoint extensions of a symmetric relation in an almost Pontryagin space. More in particular, in their compressed resolvents, \(Q\)-functions and \(h_0\)-resolvents. We give a systematic approach to each of this three topics, and show an intimate connection between the last two.