## 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

Jacob W Cooper, Daniel Kráľ, Ander Lamaison, and Samuel Mohr:

Quasirandom Latin squares

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\).

Jochen Harant and Samuel Mohr:

New bounds on domination and independence in graphs

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.

Max Hahn-Klimroth, Giulia S. Maesaka, Yannick Mogge, Samuel Mohr, and Olaf Parczyk:

Random perturbation of sparse graphs

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)\).

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.Matthias Kriesell and Samuel Mohr:

Kempe chains and rooted minors

arXiv: 1911.09998. bibTeX: download.Abstract: 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 vertex set into anticliques, that is, sets of pairwise nonadjacent 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 conjectured by the first author that 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, there exists 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 each \(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

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.

Samuel Mohr:

A construction of uniquely colourable graphs

Discrete Applied Mathematics (2021). to appear. 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.

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.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)\).

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)\).

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.

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.

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

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.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.

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:

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.