Research

The Circuit diameter of polytopes was introduced by Borgwardt, Finhold and Hemmecke as a fundamental tool for the study of circuit augmentation schemes for linear programming and for estimating combinatorial diameters. Determining the complexity of computing the circuit diameter of polytopes was posed as an open problem by Sanit\`a as well as by Kafer, and was recently reiterated by Borgwardt, Grewe, Kafer, Lee and Sanit\`a. In this paper, we solve this problem by showing that computing the circuit diameter of a polytope given in halfspace description is strongly NP-hard. To prove this result, we show that computing the combinatorial diameter of the perfect matching polytope of a bipartite graph is NP-hard. This complements a result by Sanit\`a (FOCS 2018) on the NP-hardness of computing the diameter of fractional matching polytopes and implies the new result that computing the diameter of a $\{0,1\}$-polytope is strongly NP-hard, which may be of independent interest. In our second main result, we give a precise graph-theoretic description of the monotone diameter of perfect matching polytopes and use this description to prove that computing the monotone (circuit) diameter of a given input polytope is strongly NP-hard as well. 

A graph $G$ is said to be Ramsey for a tuple of graphs $(H_1,\dots,H_r)$ if every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H_i$ in color $i$, for some $i$. A fundamental question at the intersection of Ramsey theory and the theory of random graphs is to determine the threshold at which the binomial random graph $G_{n,p}$ becomes a.a.s. Ramsey for a fixed tuple $(H_1,\dots,H_r)$, and a famous conjecture of Kohayakawa and Kreuter predicts this threshold. Earlier work of Mousset--Nenadov--Samotij, Bowtell--Hancock--Hyde, and Kuperwasser--Samotij--Wigderson has reduced this probabilistic problem to a deterministic graph decomposition conjecture. In this paper, we resolve this deterministic problem, thus proving the Kohayakawa--Kreuter conjecture. Along the way, we prove a number of novel graph decomposition results which may be of independent interest.

The Odd Hadwiger's conjecture, formulated by Gerards and Seymour in 1995, is a substantial strengthening of Hadwiger's famous coloring conjecture from 1943. We investigate whether the hierarchy of topological lower bounds on the chromatic number, introduced by Matou\v{s}ek and Ziegler (2003) and refined recently by Daneshpajouh and Meunier (2023), forms a potential avenue to a disproof of Hadwiger's conjecture or its odd-minor variant. 

In this direction, we prove that, in a very general sense, every graph $G$ that admits a topological lower bound of $t$ on its chromatic number, contains $K_{\lfloor t/2\rfloor +1}$ as an odd-minor. This solves a problem posed by Simonyi and Zsb\'{a}n [European Journal of Combinatorics, 31(8), 2110--2119 (2010)].

We also prove that if for a graph $G$ the Dol'nikov-K\v{r}\'{i}\v{z} lower bound on the chromatic number (one of the lower bounds in the aforementioned hierarchy) attains a value of at least $t$, then $G$ contains $K_t$ as a minor. 

Finally, extending results by Simonyi and Zsb\'{a}n, we show that the Odd Hadwiger's conjecture holds for Schrijver and Kneser graphs for any choice of the parameters. The latter are canonical examples of graphs for which topological lower bounds on the chromatic number are tight. 

 We show that the twin-width of every $n$-vertex $d$-regular graph is at most $n^{\frac{d-2}{2d-2}+o(1)}$ and that almost all $d$-regular graphs attain this bound. More generally, we  obtain  bounds on the twin-width of sparse Erd\H{o}s-Renyi  and regular random graphs, complementing the bounds in the denser regime due to Ahn, Chakraborti, Hendrey, Kim and Oum.

 Base polytopes of polymatroids, also known as generalized permutohedra, are polytopes whose edges are parallel to a vector of the form $\mathbf{e}_i - \mathbf{e}_j$, where the $\{\mathbf{e}_i\}_{i\in [n]}$ are the canonical basis vectors of $\mathbb{R}^n$. We consider the following computational problem: Given two vertices of a generalized permutohedron $P$, find a shortest path between them on the skeleton of $P$, where the length of a path is its number of edges. This captures many known flip distance problems, such as computing the minimum number of exchanges between two spanning trees of a graph, the rotation distance between binary search trees, the flip distance between acyclic orientations of a graph, or rectangulations of a square. 

We prove that this general problem is \NP-hard, even when restricted to very simple polymatroids in $\mathbb{R}^n$ defined by $O(n)$ inequalities. Assuming $\P\not= \NP$, this rules out the existence of a computationally efficient simplex pivoting rule that would perform a minimum number of nondegenerate pivoting steps to an optimal solution of a linear program, even when the latter defines a polymatroid.

We also prove that the shortest path problem is inapproximable when the polymatroid is specified via an evaluation oracle for a corresponding submodular function, which strengthens a recent result by Ito, Kakimura, Kamiyama, Kobayashi, Maezawa,  Nozaki, and Okamoto (ICALP'23). More precisely, we prove the \APX-hardness of the shortest path problem when the polymatroid is a hypergraphic polytope, whose vertices are in bijection with acyclic orientations of a given hypergraph. The shortest path problem then amounts to computing the flip distance between two acyclic orientations of a hypergraph. 

On the positive side, we provide a polynomial-time approximation algorithm for the problem of  computing the flip distance between two acyclic orientations of a hypergraph, where the approximation factor is the maximum codegree of the hypergraph. Our result implies in particular an exact polynomial-time algorithm for the flip distance between two acyclic orientations of any linear hypergraph.

Let $r$ be any positive integer. We prove that for every sufficiently large $k$ there exists a $k$-chromatic vertex-critical graph $G$ such that $\chi(G-R)=k$ for every set $R \subseteq E(G)$ with $|R|\le r$. 

This partially solves a problem posed by Erd\H{o}s in 1985, who asked whether the above statement holds for $k \ge 4$.

A tantalizing open problem, posed independently by Stiebitz in 1995 and by Alon in 2006, asks whether for every pair of integers $s,t \ge 1$ there exists a finite number $F(s,t)$ such that the vertex set of every digraph of minimum out-degree at least $F(s,t)$ can be partitioned into non-empty parts $A$ and $B$ such that the subdigraphs induced on $A$ and $B$ have minimum out-degree at least $s$ and $t$, respectively. In this short note, we prove that if $F(2,2)$ exists, then all the numbers $F(s,t)$ with $s,t\ge 1$ exist and satisfy $F(s,t)=\Theta(s+t)$. In consequence, the problem of Alon and Stiebitz reduces to the case $s=t=2$.Moreover, the numbers $F(s,t)$ with $s,t \ge 2$ either all exist and grow linearly, or all of them do not exist. 

We prove Menger-type results in which the obtained paths are pairwise non-adjacent, both for graphs of bounded maximum degree and, more generally, for graphs excluding a topological minor. We further show better bounds in the subcubic case, and in particular obtain a tight result for two paths using a computer-assisted proof. 

The clustered chromatic number of a graph class $\GG$ is the minimum integer $c$ such that every graph $G\in\GG$ has a $c$-colouring where each monochromatic component in $G$ has bounded size. We study the clustered chromatic number of graph classes $\GG_H^{\odd}$ defined by excluding a graph $H$ as an odd-minor. How does the structure of $H$ relate to the clustered chromatic number of $\GG_H^{\odd}$? Using a proof method by Norin, Scott, Seymour and Wood (2019), we show that the clustered chromatic number of $\GG_H^{\odd}$ is tied to the tree-depth of $H$.

Size-Ramsey numbers are a central notion in combinatorics and have been widely studied since their introduction by Erd\H{o}s, Faudree, Rousseau and Schelp in 1978. Research has mainly focused on the size-Ramsey numbers of $n$-vertex graphs with constant maximum degree $\Delta$. For example, graphs which also have constant treewidth are known to have linear size-Ramsey numbers. On the other extreme, the canonical examples of graphs of unbounded treewidth are the grid graphs, for which the best known bound has only very recently been improved from $O(n^{3/2})$ to $O(n^{5/4})$ by Conlon, Nenadov and Truji\'c. In this paper, we prove a common generalization of these results by establishing new bounds on the size-Ramsey numbers in terms of treewidth (which may grow as a function of $n$). As a special case, this yields a bound of $\tilde{O}(n^{3/2 - 1/2\Delta})$ for proper minor-closed classes of graphs. In particular, this bound applies to planar graphs, addressing a question of Wood. 

Our proof combines methods from structural graph theory and classic Ramsey-theoretic embedding techniques, taking advantage of the product structure exhibited by graphs with bounded treewidth.

Motivated by Hadwiger's conjecture, we study the problem of finding the densest possible $t$-vertex minor in graphs of average degree at least $t-1$. We show that if $G$ has average degree at least $t-1$, it contains a minor on $t$ vertices with at least $(\sqrt{2}-1-o(1))\binom{t}{2}$ edges. We show that this cannot be improved beyond $\left(\frac{3}{4}+o(1)\right)\binom{t}{2}$. Finally,  for $t\leq 6$ we exactly determine the number of edges we are guaranteed to find in the densest $t$-vertex minor in graphs of average degree at least $t-1$.

A set $\mathcal{G}$ of planar graphs on the same number $n$ of vertices is called \emph{simultaneously embeddable} if there exists a set $P$ of $n$ points in the plane such that every graph $G \in \mathcal{G}$ admits a (crossing-free) straight-line embedding with vertices placed at points of $P$. A well-known open problem from 2007 posed by Brass, Cenek, Duncan, Efrat, Erten, Ismailescu, Kobourov, Lubiw and Mitchell, asks whether for some $n$ there exists a set $\mathcal{G}$ consisting of two planar graphs on $n$ vertices that are not simultaneously embeddable. While this remains widely open, we give a short proof that for every $\varepsilon>0$ and sufficiently large $n$ there exists a collection of at most $(3+\varepsilon)\log_2(n)$ planar graphs on $n$ vertices which cannot be simultaneously embedded. This significantly improves the previous exponential bound of $O(n\cdot 4^{n/11})$ for the same problem which was recently established by Goenka, Semnani and Yip.

Scott and Seymour conjectured the existence of a function $f \colon \mathbb{N} \to \mathbb{N}$ such that, for every graph $G$ and tournament $T$ on the same vertex set, $\chi(G)\ge f(k)$ implies that $\chi(G[N_T^+(v)])\ge k$ for some vertex $v$. In this note we disprove this conjecture even if $v$ is replaced by a vertex set of size $\cO(\log{\size{V(G)}})$. As a consequence, we answer in the negative a question of Harutyunyan, Le, Thomass\'{e}, and Wu concerning the corresponding statement where the graph $G$ is replaced by another tournament, and disprove a related conjecture of Nguyen, Scott, and Seymour. We also show that the setting where chromatic number is replaced by degeneracy exhibits a quite different behaviour.

For any positive edge density $p$, a random graph in the \erdos-\renyi{} $G_{n,p}$ model is connected with non-zero probability, since all edges are mutually independent. We consider random graph models in which edges that do not share endpoints are independent while incident edges may be dependent and ask: what is the minimum probability $\rho(n)$, such that for any distribution $\mathcal{G}$ (in this model) on graphs with $n$ vertices in which each potential edge has a marginal probability of being present at least $\rho(n)$, a graph drawn from $\mathcal{G}$ is connected with non-zero probability?

As it turns out, the condition ``edges that do not share endpoints are independent'' needs to be clarified and the answer to the question above is sensitive to the specification. In fact, we formalize this intuitive description into a strict hierarchy of five independence conditions, which we show to have at least three different behaviors for the threshold $\rho(n)$. For each condition, we provide upper and lower bounds for $\rho(n)$. In the strongest condition, the \emph{coloring model} (which includes, e.g., random geometric graphs), we show that $\rho(n)\rightarrow 2-\phi\approx 0.38$ for $n\rightarrow\infty$, proving a conjecture by Badakhshian, Falgas-Ravry, and Sharifzadeh. This separates the coloring models from the weaker independence conditions we consider, as there we prove that $\rho(n)>0.5-o(n)$.

In stark contrast to the coloring model, for our weakest independence condition --- pairwise independence of non-adjacent edges --- we show that $\rho(n)$ lies within $O(1/n^2)$ of the threshold $1-2/n$ for completely arbitrary distributions.

Given a graph $H$, let us denote by $f_\chi(H)$ and $f_\ell(H)$, respectively, the maximum chromatic number and the maximum list chromatic number of $H$-minor-free graphs. Hadwiger's famous coloring conjecture from 1943 asserts that $f_\chi(K_t)=t-1$ for every $t \ge 2$. A closely related problem that has received significant attention in the past concerns the list chromatic number of $K_t$-minor-free graphs. In this setting it is known that $f_\ell(K_t)>t-1$ for every $t \ge 5$, while the best known asymptotic bounds are $2t-o(t) \le f_\ell(K_t) \le O(t (\log \log t)^6)$. Thus, the list chromatic number of $K_t$-minor-free graphs is separated from the conjectured value $t-1$ for the chromatic number by at least a constant factor. A well-known and natural relaxation of Hadwiger's conjecture, proposed by Seymour, asks to prove that $H$-minor-free graphs are $(\vv(H)-1)$-colorable, for a given (possibly non-complete) graph $H$. In this paper, we explore the limits of a list coloring approach to this so-called $H$-Hadwiger's conjecture, by proving new general lower bounds on $f_\ell(H)$. Our main results are:

-For every $\varepsilon>0$ and all sufficiently large graphs $H$ we have $f_\ell(H)\ge (1-\varepsilon)(\vv(H)+\kappa(H))$, where $\kappa(H)$ denotes the vertex-connectivity of $H$. 

-For every $\varepsilon>0$ there exists $C=C(\varepsilon)>0$ such that asymptotically almost every $n$-vertex graph $H$ with $\left\lceil C n\log n\right\rceil$ edges satisfies $f_\ell(H)\ge (2-\varepsilon)n$. 

The first result generalizes recent results on complete and complete bipartite graphs and shows that the list chromatic number of $H$-minor-free graphs is separated from the desired value of $(\vv(H)-1)$ by a constant factor for all large graphs $H$ of linear connectivity. The second result is conceptually stronger, telling us that almost all graphs with superlogarithmic average degree satisfy $f_\ell(H)\ge (2-o(1))\vv(H)$ and thus, with few exceptions the graphs $H$ for which $f_\ell(H)$ is close to $(\vv(H)-1)$ consist of rather sparse graphs.

A finite set $P $ of points in the plane is $n$-universal with respect to a class $\mathcal{C}$ of planar graphs if every $n$-vertex graph in $\mathcal{C}$ admits a crossing-free straight-line drawing with vertices at points of $P$. For the class of all planar graphs the best known upper bound on the size of a universal point set is quadratic and the best known lower bound is linear in~$n$. Some classes of planar graphs are known to admit universal point sets of near linear size, however, there are no truly linear bounds for interesting classes beyond outerplanar graphs. In this paper, we show that there is a universal point set of size $2n-2$ for the class of bipartite planar graphs with $n$ vertices. The same point set is also universal for the class of $n$-vertex planar graphs of maximum degree~$3$. The point set used for the results is what we call an exploding double chain, and we prove that this point set allows planar straight-line embeddings of many more planar graphs, namely of all subgraphs of  planar graphs admitting a one-sided Hamiltonian cycle. 

The result for bipartite graphs also implies that every $n$-vertex plane graph has a 1-bend drawing all whose bends and vertices are contained in a specific point set of size $4n-6$, this improves a bound of $6n-10$ for the same problem by Löffler and Tóth.

In 2006, Noga Alon~\cite{alon} raised the following open problem: Does there exist an absolute constant $c>0$ such that every $2n$-vertex digraph with minimum out-degree at least $s$ contains an $n$-vertex subdigraph with minimum out-degree at least $\frac{s}{2}-c$~?

In this note, we answer this natural question in the negative, by showing that for arbitrarily large values of $n$ there exists a $2n$-vertex tournament with minimum out-degree $s=n-1$, in which every $n$-vertex subdigraph contains a vertex of out-degree at most $\frac{s}{2}-\left(\frac{1}{2}+o(1)\right)\log_3(s)$. 

We consider the computational problem of finding short paths in the skeleton of the perfect matching polytope of a bipartite graph. We prove that unless $\P=\NP$, there is no polynomial-time algorithm that computes a path of constant length between two vertices at distance two of the perfect matching polytope of a bipartite graph. Conditioned on $\P\neq\NP$, this disproves a conjecture by Ito, Kakimura, Kamiyama, Kobayashi and Okamoto [SIAM Journal on Discrete Mathematics, 36(2), pp. 1102-1123 (2022)]. Assuming the Exponential Time Hypothesis we prove the stronger result that there exists no polynomial-time algorithm computing a path of length at most $\left(\frac{1}{4}-o(1)\right)\frac{\log N}{\log \log N}$ between two vertices at distance two of the perfect matching polytope of an $N$-vertex bipartite graph. These results remain true if the bipartite graph is restricted to be of maximum degree three. 

The above has the following interesting implication for the performance of pivot rules for the simplex algorithm on simply-structured combinatorial polytopes: If $\P\neq\NP$, then for every simplex pivot rule executable in polynomial time and every constant $k \in \mathbb{N}$ there exists a linear program on a perfect matching polytope and a starting vertex of the polytope such that the optimal solution can be reached in two monotone steps from the starting vertex, yet the pivot rule will require at least $k$ steps to reach the optimal solution. This result remains true in the more general setting of pivot rules for so-called circuit-augmentation algorithms.

Hadwiger's famous coloring conjecture states that every $t$-chromatic graph contains a $K_t$-minor. Holroyd [Bull. London Math. Soc. 29, (1997), pp. 139--144] conjectured the following strengthening of Hadwiger's conjecture: If $G$ is a $t$-chromatic graph and $S \subseteq V(G)$ takes all colors in every $t$-coloring of $G$, then $G$ contains a $K_t$-minor \emph{rooted at $S$}. 

We prove this conjecture in the first open case of $t=4$. Notably, our result also directly implies a stronger version of Hadwiger's conjecture for $5$-chromatic graphs as follows:

Every $5$-chromatic graph contains a $K_5$-minor with a singleton branch-set. In fact, in a $5$-vertex-critical graph we may specify the singleton branch-set to be any vertex of the graph.

We prove that for every digraph $F$ and every assignment of pairs of integers $(r_e,q_e)_{e \in A(F)}$ to its arcs there exists an integer $N$ such that every digraph $D$ with dichromatic number greater than $N$ contains a subdivision of $F$ in which $e$ is subdivided into a directed path of length congruent to $r_e$ modulo $q_e$, for every $e \in A(F)$.

This generalizes to the directed setting the analogous result by Thomassen~\cite{thomassen} for undirected graphs, and at the same time yields a novel short proof of his result.

Gerards and Seymour conjectured in 1995 that every graph $G$ contains $K_{\chi(G)}$ as an odd-minor, this strengthening of Hadwiger's conjecture is known as the \emph{Odd Hadwiger's conjecture}. We give a short proof that this conjecture holds for line-graphs of simple graphs.

Given an integer $k$ and a graph where every edge is colored either red or blue, the goal of the exact matching problem is to find a perfect matching with the property that exactly $k$ of its edges are red. Soon after Papadimitriou and Yannakakis (JACM 1982) introduced the problem, a randomized polynomial-time algorithm solving the problem was described by Mulmuley et al. (Combinatorica 1987). Despite a lot of effort, it is still not known today whether a deterministic polynomial-time algorithm exists. This makes the exact matching problem an important candidate to test the popular conjecture that the complexity classes $\textsc{P}$ and $\textsc{RP}$ are equal. In a recent article (MFCS 2022), progress was made towards this goal by showing that for bipartite graphs of bounded bipartite independence number, a polynomial time algorithm exists. In terms of parameterized complexity, this algorithm was an XP-algorithm parameterized by the bipartite independence number. In this article, we introduce novel algorithmic techniques that allow us to obtain an FPT-algorithm. If the input is a general graph we show that one can at least compute a perfect matching $M$ which has the correct number of red edges modulo 2, in polynomial time. This is motivated by our last result, in which we prove that an FPT algorithm for general graphs, parameterized by the independence number, reduces to the problem of finding in polynomial time a perfect matching $M$ with at most $k$ red edges and the correct number of red edges modulo 2.

Hadwiger's conjecture, among the most famous open problems in graph theory, states that every graph that does not contain $K_t$ as a minor is properly $(t-1)$-colorable. The purpose of this work is to demonstrate that a natural extension of Hadwiger's problem to hypergraph coloring exists, and to derive some first partial results and applications.

Generalizing ordinary graph minors to hypergraphs, we say that a hypergraph $H_1$ is a minor of a hypergraph $H_2$, if a hypergraph isomorphic to $H_1$ can be obtained from $H_2$ via a finite sequence of the following operations: 

-deleting vertices and hyperedges,

-contracting a hyperedge (i.e., merging the vertices of the hyperedge into a single vertex).

First we show that a weak extension of Hadwiger's conjecture to hypergraphs holds true: For every $t \ge 1$, there exists a finite (smallest) integer $h(t)$ such that every hypergraph with no $K_t$-minor is $h(t)$-colorable, and we prove

$$\left\lceil\frac{3}{2}(t-1)\right\rceil \le h(t) \le 2g(t)$$ where $g(t)$ denotes the maximum chromatic number of graphs with no $K_t$-minor. Using the recent result by Delcourt and Postle that $g(t)=O(t \log \log t)$, this yields $h(t)=O(t \log \log t)$.

We further conjecture that $h(t)=\left\lceil\frac{3}{2}(t-1)\right\rceil$, i.e., that every hypergraph with no $K_t$-minor is $\left\lceil\frac{3}{2}(t-1)\right\rceil$-colorable for all $t \ge 1$, and prove this conjecture for all hypergraphs with independence number at most $2$. 

By considering special classes of hypergraphs, the above additionally has some interesting applications for ordinary graph coloring, such as:

-every graph $G$ is $O(k t \log \log t)$-colorable or contains a $K_t$-minor model all whose branch-sets are $k$-edge-connected, 

-every graph $G$ is $O( q t \log \log t )$-colorable or contains a $K_t$-minor model all whose branch-sets are modulo-$q$-connected (i.e., every pair of vertices in the same branch-set has a connecting path of prescribed length modulo $q$),

-by considering cycle hypergraphs of digraphs, we obtain known results on strong minors in digraphs with large dichromatic number as special cases. We also construct digraphs with dichromatic number $\left\lceil\frac{3}{2}(t-1)\right\rceil$ not containing the complete digraph on $t$ vertices as a strong minor, thus answering a question by M\'{e}sz\'{a}ros and the author in the negative.

Felsner, Hurtado, Noy and Streinu (2000) conjectured that arrangement graphs of simple great-circle arrangements have chromatic number at most $3$. Motivated by this conjecture, we study the colorability of arrangement graphs for different classes of arrangements of (pseudo-)circles. In this paper the conjecture is verified for $\triangle$-saturated pseudocircle arrangements, i.e., for arrangements where one color class of the 2-coloring of faces consists of triangles only, as well as for further classes of (pseudo-)circle arrangements. These results are complemented by a construction which maps $\triangle$-saturated arrangements with a pentagonal face to arrangements with 4-chromatic 4-regular arrangement graphs. This ``corona'' construction has similarities with the ``crowning'' construction introduced by Koester (1985). Based on exhaustive experiments with small arrangements we propose three strengthenings of the original conjecture. We also investigate fractional colorings. It is shown that the arrangement graph of every arrangement $\mathcal{A}$ of pairwise intersecting pseudocircles is ``close'' to being $3$-colorable. More precisely, the fractional chromatic number $\chi_f(\mathcal{A})$ of the arrangement graph is bounded from above by $\chi_f(\mathcal{A}) \le 3+O(\frac{1}{n})$, where $n$ is the number of pseudocircles of $\mathcal{A}$. 

Furthermore, we construct an infinite family of $4$-edge-critical $4$-regular planar graphs which are fractionally $3$-colorable. This disproves a conjecture of Gimbel, K\"{u}ndgen, Li, and Thomassen (2019).

Given a constant $\alpha>0$, an $n$-vertex graph is called an \emph{$\alpha$-expander} if every set $X$ of at most $n/2$ vertices in $G$ has an external neighborhood of size at least $\alpha|X|$. Addressing a question posed by Friedman and Krivelevich in [Combinatorica, 41(1), (2021), pp. 53--74], we prove the following result: 

Let $k>1$ be an integer with smallest prime divisor $p$. Then for $\alpha>\frac{1}{p-1}$ every sufficiently large $\alpha$-expanding graph contains cycles of length congruent to any given residue modulo $k$. 

This result is almost best possible, in the following sense: There exists an absolute constant $c>0$ such that for every integer $k$ with smallest prime divisor $p$ and for every positive $\alpha<\frac{c}{p-1}$, there exist arbitrarily large $\alpha$-expanding graphs with no cycles of length $r$ modulo $k$, for some $r \in \{0,\ldots,k-1\}$. 

Strengthening Hadwiger's conjecture, Gerards and Seymour conjectured in 1995 that every graph with no odd $K_t$-minor is properly $(t-1)$-colorable, this is known as the Odd Hadwiger's conjecture. 

We prove a relaxation of the above conjecture, namely we show that every graph with no odd $K_t$-minor admits a vertex $(2t-2)$-coloring such that all monochromatic components have size at most $\lceil \frac{1}{2}(t-2) \rceil$. The bound on the number of colors is optimal up to a factor of $2$, improves previous bounds for the same problem by Kawarabayashi (2008), Kang and Oum~(2019), Liu and Wood (2021), and strengthens a result by van den Heuvel and Wood (2018), who showed that the above conclusion holds under the more restrictive assumption that the graph is $K_t$-minor free. In addition, the bound on the component-size in our result is much smaller than those of previous results, in which the dependency on $t$ was non-explicit.

Our short proof combines the method by van den Heuvel and Wood for $K_t$-minor free graphs with some additional ideas, which make the extension to odd $K_t$-minor free graphs possible.

In the Exact Matching Problem (EM), we are given a graph equipped with a fixed coloring of its edges with two colors (red and blue), as well as a positive integer k. The task is then to decide whether the given graph contains a perfect matching exactly k of whose edges have color red. EM generalizes several important algorithmic problems such as perfect matching and restricted minimum weight spanning tree problems.

When introducing the problem in 1982, Papadimitriou and Yannakakis conjectured EM to be NP-complete. Later however, Mulmuley et al. presented a randomized polynomial time algorithm for EM, which puts EM in RP. Given that to decide whether or not RP=P represents a big open challenge in complexity theory, this makes it unlikely for EM to be NP-complete, and in fact indicates the possibility of a deterministic polynomial time algorithm. EM remains one of the few natural combinatorial problems in RP which are not known to be contained in P, making it an interesting instance for testing the hypothesis RP=P.

Despite EM being quite well-known, attempts to devise deterministic polynomial algorithms have remained illusive during the last 40 years and progress has been lacking even for very restrictive classes of input graphs. In this paper we push the frontier of positive results forward by proving that EM can be solved in deterministic polynomial time for input graphs of bounded independence number, and for bipartite input graphs of bounded bipartite independence number. This generalizes previous positive results for complete (bipartite) graphs which were the only known results for EM on dense graphs. 

Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian. 

A graph, other than the path of length three, is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette's Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity.

As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. [Hamiltonian Cycles in Cubic 3-Connected Bipartite Planar Graphs, JCTB, 1985]. These allow us to check whether a graph we generated is a brace.

We characterize all digraphs $H$ such that orientations of chordal graphs with no induced copy of $H$ have bounded dichromatic number.

In a 2001 survey article about list coloring, Woodall conjectured that for every pair of integers $s,t \ge 1$, all graphs without a $K_{s,t}$-minor are $(s+t-1)$-choosable.

In this note we refute this conjecture in a strong form: We prove that for every choice of constants $\varepsilon>0$ and $C \ge 1$ there exists $N=N(\varepsilon,C) \in \mathbb{N}$ such that for all integers $s,t $ with $N \le s \le t \le Cs$ there exists a graph without a $K_{s,t}$-minor and list chromatic number greater than $(1-\varepsilon)(2s+t)$. 

Assume $n$ players are placed on the $n$ vertices of a graph $G$. The following game was introduced by Winkler: An adversary puts a hat on each player, where each hat has a colour out of $q$ available colours. The players can see the hat of each of their neighbours in $G$, but not their own hat. Using a prediscussed guessing strategy, the players then simultaneously guess the colour of their hat. The players win if at least one of them guesses correctly, else the adversary wins. The largest integer $q$ such that there is a winning strategy for the players is denoted by $\HG(G)$, and this is called the hat guessing number of $G$.

Although this game has received a lot of attention in the recent years, not much is known about how the hat guessing number relates to other graph parameters. For instance, a natural open question is whether the hat guessing number can be bounded from above in terms of degeneracy. In this paper, we prove that the hat guessing number of a graph can be bounded from above in terms of a related notion, which we call strong degeneracy. We further give an exact characterisation of graphs with bounded strong degeneracy. As a consequence, we significantly improve the best known upper bound on the hat guessing number of outerplanar graphs from $2^{125000}$ to $40$, and further derive upper bounds on the hat guessing number for any class of $K_{2,s}$-free graphs with bounded expansion, such as the class of $C_4$-free planar graphs, more generally $K_{2,s}$-free graphs with bounded Hadwiger number or without a $K_t$-subdivision, and for Erd\H{o}s-R\'enyi random graphs with constant average degree

In this paper, we disprove the long-standing conjecture that any complete geometric graph on 2n vertices can be partitioned into n plane spanning trees. Our construction is based on so-called bumpy wheel sets. We fully characterize which bumpy wheels can and in particular which cannot be partitioned into plane spanning trees (or even into arbitrary plane subgraphs).

Furthermore, we show a sufficient condition for generalized wheels to not admit a partition into plane spanning trees, and give a complete characterization when they admit a partition into plane spanning double stars.

Finally, we initiate the study of partitions into beyond planar subgraphs, namely into k-planar and k-quasi-planar subgraphs and obtain first bounds on the number of subgraphs required in this setting. 

Alon and Krivelevich proved that for every $n$-vertex subcubic graph $H$ and every integer $q \ge 2$ there exists a (smallest) integer $f=f(H,q)$ such that every $K_f$-minor contains a subdivision of $H$ in which the length of every subdivision-path is divisible by $q$. Improving their superexponential bound, we show that $f(H,q) \le \frac{21}{2}qn+8n+14q$, which is optimal up to a constant multiplicative factor.

Hadwiger's conjecture asserts that every graph without a $K_t$-minor is $(t-1)$-colorable. It is known that the exact version of Hadwiger's conjecture does not extend to list coloring, but it has been conjectured by Kawarabayashi and Mohar (2007) that there exists a constant $c$ such that every graph with no $K_t$-minor has list chromatic number at most $ct$. More specifically, they also conjectured that this holds for $c=\frac{3}{2}$. 

Refuting the latter conjecture, we show that the maximum list chromatic number of graphs with no $K_t$-minor is at least $(2-o(1))t$, and hence $c \ge 2$ in the above conjecture is necessary. This improves the previous best lower bound by  Bar\'{a}t, Joret and Wood (2011), who proved that $c \ge \frac{4}{3}$. Our lower-bound examples are obtained via the probabilistic method.

Hadwiger's conjecture states that every $K_t$-minor free graph is $(t-1)$-colorable. A qualitative strengthening of this conjecture raised by Gerards and Seymour, known as the \emph{Odd Hadwiger's conjecture}, states similarly that every graph with no \emph{odd $K_t$-minor} is $(t-1)$-colorable. For both conjectures, their asymptotic relaxations remain open, i.e., whether an upper bound on the chromatic number of the form $Ct$ for some constant $C>0$ exists. 

We show that if every graph without a $K_t$-minor is $f(t)$-colorable, then every graph without an odd $K_t$-minor is $2f(t)$-colorable. As a direct corollary, we present a new state of the art-bound $O(t\log\log t)$ for the chromatic number of graphs with no odd $K_t$-minor. Moreover, the short proof of our result substantially simplifies the proofs of all the previous asymptotic bounds for the chromatic number of odd $K_t$-minor free graphs established in a sequence of papers during the last 12 years.

Given a non-trivial finite Abelian group $(A,+)$, let $n(A) \ge 2$ be the smallest integer such that for every labelling of the arcs of the bidirected complete graph $\bivec{K}_{n(A)}$ with elements from $A$ there exists a directed cycle for which the sum of the arc-labels is zero. The problem of determining $n(\mathbb{Z}_q)$ for integers $q \ge 2$ was recently considered by Alon and Krivelevich, who proved that $n(\mathbb{Z}_q)=O(q \log q)$. Here we improve their result and show that $n(\mathbb{Z}_q)$ grows linearly. More generally we prove that for every finite Abelian group $A$ we have $n(A) \le 8|A|$, while if $|A|$ is prime then $n(A) \le \frac{3}{2}|A|$. 

As a corollary we obtain that every $K_{16q}$-minor contains a cycle of length divisible by $q$ for every integer $q \ge 2$, which improves another result by Alon and Krivelevich.

We prove a conjecture by Aboulker, Charbit and Naserasr by showing that every oriented graph in which the out-neighborhood of every vertex induces a transitive tournament can be partitioned into two acyclic induced subdigraphs. We prove multiple extensions of this result to larger classes of digraphs defined by a finite list of forbidden induced subdigraphs. 

We thereby resolve several special cases of an extension of the famous Gy\'{a}rf\'{a}s-Sumner conjecture to directed graphs due to Aboulker et al.

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 simple digraph admits an $F$-free $k$-coloring. Our main focus is on the restriction of the problem to planar input digraphs, where it is only interesting to study the cases $k \in \{2,3\}$. From known results it follows that for every fixed digraph $F$ whose underlying graph is not a forest, every planar digraph $D$ admits an $F$-free $2$-coloring, and that for every fixed digraph $F$ with $\Delta(F) \ge 3$, every oriented planar graph $D$ admits an $F$-free $3$-coloring. We show in contrast, that

-if $F$ is an orientation of a path of length at least $2$, then it is \NP-hard to decide whether an \emph{acyclic and planar} input digraph $D$ admits an $F$-free $2$-coloring.

-if $F$ is an orientation of a path of length at least $1$, then it is \NP-hard to decide whether an \emph{acyclic and planar} input digraph $D$ admits an $F$-free $3$-coloring.

The dichromatic number $\vec{\chi}(D)$ of a digraph $D$ is the smallest $k$ for which it admits a $k$-coloring where every color class induces an acyclic subgraph. 

Inspired by Hadwiger's conjecture for undirected graphs, several groups of authors have recently studied the containment of complete directed minors in digraphs with given dichromatic number. In this note we exhibit a relation of these problems to Hadwiger's conjecture. Exploiting this relation, we show that every directed graph excluding the complete digraph $\bivec{K}_t$ of order $t$ as a strong minor or as a butterfly-minor is $O(t(\log \log t)^6)$-colorable. 

This answers a question by Axenovich, Gir\~{a}o, Snyder and Weber, who proved an upper bound of $t4^t$ for the same problem. A further consequence of our results is that every digraph of dichromatic number $22n$ contains a subdivision of every $n$-vertex subcubic digraph, which makes progress on a set of problems raised by Aboulker, Cohen, Havet, Lochet, Moura and Thomassé.

A conjecture by Lichiardopol~\cite{lich} states that for every $k \ge 1$ there exists an integer $g(k)$ such that every digraph of minimum out-degree at least $g(k)$ contains $k$ vertex-disjoint directed cycles of pairwise distinct lengths.

Motivated by Lichiardopol's conjecture, we study the existence of vertex-disjoint directed cycles satisfying length constraints in digraphs of large connectivity or large minimum degree. Our main result is that for every $k \in \mathbb{N}$, there exists $s(k) \in \mathbb{N}$ such that every strongly $s(k)$-connected digraph contains $k$ vertex-disjoint directed cycles of pairwise distinct lengths. In contrast, for every $k \in \mathbb{N}$ we construct a strongly $k$-connected digraph containing no two vertex- or arc-disjoint directed cycles of the same length. 

It is an open problem whether $g(3)$ exists. Here we prove the existence of an integer $K$ such that every digraph of minimum out- and in-degree at least $K$ contains $3$ vertex-disjoint directed cycles of pairwise distinct lengths. 

In this paper we generalise the even directed cycle problem, which asks whether a given digraph contains a directed cycle of even length, to orientations of regular matroids. We define non-even oriented matroids generalising non-even digraphs, which played a central role in resolving the computational complexity of the even dicycle problem. Then we show that the problem of detecting an even directed circuit in a regular matroid is polynomially equivalent to the recognition of non-even oriented matroids. Our main result is a precise characterisation of the class of non-even oriented cographic matroids in terms of forbidden minors, which complements an existing characterisation of non-even oriented graphic matroids by Seymour and Thomassen. 

In 1985, Mader conjectured that for every acyclic digraph $F$ there exists $K=K(F)$ such that every digraph $D$ with minimum out-degree at least $K$ contains a subdivision of $F$. This conjecture remains widely open, even for digraphs $F$ on five vertices. Recently, Aboulker, Cohen, Havet, Lochet, Moura and Thomass\'{e} studied special cases of Mader's problem and made the following conjecture:

For every $\ell \geq 2$ there exists $K = K(\ell)$ such that every digraph $D$ with minimum out-degree at least $K$ contains a subdivision of every orientation of a cycle of length $\ell$. 

We prove this conjecture and answer further open questions raised by Aboulker et al.

We investigate bounds on the dichromatic number of digraphs which avoid a fixed digraph as a topological minor. For a digraph $F$, denote by $\text{mader}_{\vec{\chi}}(F)$ the smallest integer $k$ such that every $k$-dichromatic digraph contains a subdivision of $F$.

As our first main result, we prove that if $F$ is an orientation of a cycle then $\text{mader}_{\vec{\chi}}(F)=v(F)$. This settles a conjecture of Aboulker, Cohen, Havet, Lochet, Moura and Thomass\'{e}. We also extend this result to the more general class of orientations of cactus graphs, and to bioriented forests. 

Our second main result is that $\text{mader}_{\vec{\chi}}(F)=4$ for every tournament $F$ of order $4$. This is an extension of the classical result by Dirac that $4$-chromatic graphs contain a $K_4$-subdivision to directed graphs.

We consider cell colorings of drawings of graphs in the plane. Given a multi-graph $G$ together with a drawing $\Gamma(G)$ in the plane with only finitely many crossings, we define a cell $k$-coloring of $\Gamma(G)$ to be a coloring of the maximal connected regions of the drawing, the cells, with $k$ colors such that adjacent cells have different colors. By the $4$-color theorem, every drawing of a bridgeless graph has a cell $4$-coloring. A drawing of a graph is cell $2$-colorable if and only if the underlying graph is Eulerian. We show that every graph without degree 1 vertices admits a cell $3$-colorable drawing. This leads to the natural question which abstract graphs have the property that each of their drawings has a cell $3$-coloring. We say that such a graph is universally cell $3$-colorable. We show that every $4$-edge-connected graph and every graph admitting a nowhere-zero $3$-flow is universally cell $3$-colorable.

We also discuss circumstances under which universal cell $3$-colorability guarantees the existence of a nowhere-zero $3$-flow. On the negative side, we present an infinite family of universally cell $3$-colorable graphs without a nowhere-zero $3$-flow. On the positive side, we formulate a conjecture which has a surprising relation to a famous open problem by Tutte known as the $3$-flow-conjecture. We prove our conjecture for subcubic and for $K_{3,3}$-minor-free graphs.

In this article we discuss classical theorems from Convex Geometry in the context of topological drawings and beyond. 

In a simple topological drawing of the complete graph~$K_n$,  any two edges share at most one point: either a common vertex or a point where they cross. Triangles of simple topological drawings can be viewed as convex sets. This gives a link to convex geometry. 

As our main result, we present a generalization of Kirchberger's Theorem that is of purely combinatorial nature. It turned out that this classical theorem also applies to ``generalized signotopes'' -- a combinatorial generalization of simple topological drawings, which we introduce and investigate in the course of this article.  As indicated by the name they are a generalization of signotopes, a structure studied in the context of encodings for arrangements of pseudolines.

We also present a family of simple topological drawings with arbitrarily large Helly number, and a new proof of a topological generalization of Carath\'{e}odory's Theorem in the plane and discuss further classical theorems from Convex Geometry in the context of simple topological drawings. 

In this article we discuss classical theorems from Convex Geometry in the context of topological drawings and beyond. 

In a simple topological drawing of the complete graph~$K_n$,  any two edges share at most one point: either a common vertex or a point where they cross. Triangles of simple topological drawings can be viewed as convex sets. This gives a link to convex geometry. 

As our main result, we present a generalization of Kirchberger's Theorem that is of purely combinatorial nature. It turned out that this classical theorem also applies to ``generalized signotopes'' -- a combinatorial generalization of simple topological drawings, which we introduce and investigate in the course of this article.  As indicated by the name they are a generalization of signotopes, a structure studied in the context of encodings for arrangements of pseudolines.

We also present a family of simple topological drawings with arbitrarily large Helly number, and a new proof of a topological generalization of Carath\'{e}odory's Theorem in the plane and discuss further classical theorems from Convex Geometry in the context of simple topological drawings. 

The digirth of a digraph is the length of a shortest directed cycle. The dichromatic number $\vec{\chi}(D)$ of a digraph $D$ is the smallest size of a partition of the vertex-set into subsets inducing acyclic subgraphs.

A conjecture by Harutyunyan and Mohar states that $\vec{\chi}(D) \le \lceil\frac{\Delta}{4}\rceil+1$ for every digraph $D$ of digirth at least $3$ and maximum degree $\Delta$. The best known partial result by Golowich shows that $\vec{\chi}(D) \le \frac{2}{5}\Delta+O(1)$. 

In this short note we prove for every $g \ge 2$ that if $D$ is a digraph of digirth at least $2g-1$ and maximum degree $\Delta$, then $\vec{\chi}(D) \le (\frac{1}{3}+\frac{1}{3g}) \Delta + O_g(1)$. This improves the bound of Golowich for digraphs without directed cycles of length at most $10$.

Let $\LL$ be an arrangement of $n$ lines in the Euclidean plane.  The $k$-level of $\LL$ consists of all vertices $v$ of the arrangement which have exactly $k$ lines of $\LL$ passing below $v$. The complexity (the maximum size) of the $k$-level in a line arrangement has been widely studied.  In 1998 Dey proved an upper bound of $O(n\cdot (k+1)^{1/3})$.  Due to the correspondence between lines in the plane and great-circles on the sphere, the asymptotic bounds carry over to arrangements of great-circles on the sphere, where the $k$-level denotes the vertices at distance at most $k$ to a marked cell, the south pole.

We prove an upper bound of $O((k+1)^2)$ on the expected complexity of the $k$-level in great-circle arrangements if the south pole is chosen uniformly at random among all cells. 

We also consider arrangements of great $(d-1)$-spheres on the sphere $\SS^d$ which are orthogonal to a set of random points on $\SS^d$. In this model, we prove that the expected complexity of the $k$-level is of order $\Theta((k+1)^{d-1})$.

A majority coloring of a directed graph is a vertex-coloring in which every vertex has the same color as at most half of its out-neighbors. Kreutzer, Oum, Seymour, van der Zypen and Wood \cite{kreutzer} proved that every digraph has a majority $4$-coloring and conjectured that every digraph admits a majority $3$-coloring. 

We verify this conjecture for digraphs with chromatic number at most $6$ or dichromatic number at most $3$. We obtain analogous results for list coloring: We show that every digraph with list chromatic number at most $6$ or list dichromatic number at most $3$ is majority $3$-choosable. We deduce that digraphs with maximum out-degree at most $4$ or maximum degree at most $7$ are majority $3$-choosable.

On the way to these results we investigate digraphs admitting a majority $2$-coloring. We show that every digraph without odd directed cycles is majority $2$-choosable. We answer an open question posed in \cite{kreutzer} negatively, by showing that deciding whether a given digraph is majority $2$-colorable is NP-complete.  

Finally we deal with a fractional relaxation of majority coloring proposed in \cite{kreutzer} and show that every digraph has a fractional majority 3.9602-coloring. We show that every digraph $D$ with minimum out-degree $\Omega\left((1/\varepsilon)^2\ln(1/\varepsilon)\right)$ has a fractional  majority $(2+\varepsilon)$-coloring. 

Neumann-Lara and \u{S}krekovski conjectured that every planar digraph is $2$-colourable. We show that this conjecture is equivalent to the more general statement that all oriented $K_5$-minor-free graphs are $2$-colourable.

Many well-known NP-hard algorithmic problems on directed graphs resist efficient parametrisations with most known width measures for directed graphs, such as directed treewidth, DAG-width, Kelly-width and many others. 

While these focus on measuring how close a digraph is to an oriented tree resp. a directed acyclic graph, in this paper, we investigate directed modular width as a parameter, which is closer to the concept of clique-width. We investigate applications of modular decompositions of directed graphs to a wide range of algorithmic problems and derive FPT-algorithms for several well-known digraph-specific NP-hard problems, namely minimum (weight) directed feedback vertex set, minimum (weight) directed dominating set, digraph colouring, directed Hamiltonian path/cycle, partitioning into paths, (capacitated) vertex-disjoint directed paths, and the directed subgraph homeomorphism problem.

The latter yields a polynomial-time algorithm for detecting topological minors in digraphs of bounded directed modular width.

Finally we illustrate that also other structural digraph parameters, such as directed pathwidth and the cycle-rank can be computed efficiently using directed modular width as a parameter.

We study two parameters that arise from the dichromatic number and the vertex-arboricity in the same way that the achromatic number comes from the chromatic number.

The adichromatic number of a digraph is the largest number of colors its vertices can be colored with such that every color induces an acyclic subdigraph but merging any two colors yields a monochromatic directed cycle. Similarly, the a-vertex arboricity of an undirected graph is the largest number of colors that can be used such that every color induces a forest but merging any two yields a monochromatic cycle. 

We study the relation between these parameters and their behavior with respect to other classical parameters such as degeneracy and most importantly feedback vertex sets.

A colouring of a digraph as defined by Neumann-Lara in 1982 is a vertex-colouring such that no monochromatic directed cycles exist. The minimal number of colours required for such a colouring of a loopless digraph is defined to be its dichromatic number. This quantity has been widely studied in the last decades and can be considered as a natural directed analogue of the chromatic number of a graph. 

A digraph $D$ is called even if for every $0$-$1$-weighting of the edges it contains a directed cycle of even total weight. We show that every non-even digraph has dichromatic number at most $2$ and an optimal colouring can be found in polynomial time.

We strengthen a previously known NP-hardness result by showing that deciding whether a directed graph is $2$-colourable remains NP-hard even if it contains a feedback vertex set of bounded size.

Flip graphs are a ubiquitous class of graphs, which encode relations induced on a set of combinatorial objects by elementary, local changes. Skeletons of associahedra, for instance, are the graphs induced by quadrilateral flips in triangulations of a convex polygon. For some definition of a flip graph, a natural computational problem to consider is the flip distance: Given two objects, what is the minimum number of flips needed to transform one into the other?

We consider flip graphs on orientations of simple graphs, where flips consist of reversing the direction of some edges. More precisely, we consider so-called $\alpha$-orientations of a graph $G$, in which every vertex $v$ has a specified outdegree $\alpha(v)$, and a flip consists of reversing all edges of a directed cycle. We prove that deciding whether the flip distance between two $\alpha$-orientations of a planar graph $G$ is at most two is \NP-complete. This also holds in the special case of perfect matchings, where flips involve alternating cycles. This problem amounts to finding geodesics on the common base polytope of two partition matroids, or, alternatively, on an alcoved polytope. It therefore provides an interesting example of a flip distance question that is computationally intractable despite having a natural interpretation as a geodesic on a nicely structured combinatorial polytope.

We also consider the dual question of the flip distance between graph orientations in which every cycle has a specified number of forward edges, and a flip is the reversal of all edges in a minimal directed cut. In general, the problem remains hard. However, if we restrict to flips that only change sinks into sources, or vice-versa, then the problem can be solved in polynomial time. Here we exploit the fact that the flip graph is the cover graph of a distributive lattice. This generalizes a recent result from Zhang, Qian, and Zhang (Acta. Math. Sin.-English Ser., 2019).

We investigate which planar point sets allow simultaneous straight-line embeddings of all planar graphs on a fixed number of vertices. We first show that at least $(1.293-o(1))n$ points are required to find a straight-line drawing of each $n$-vertex planar graph (vertices are drawn as the given points); this improves the previous best constant $1.235$ by Kurowski (2004).

Our second main result is based on exhaustive computer search: We show that no set of 11 points exists, on which all planar 11-vertex graphs can be simultaneously drawn plane straight-line. This strengthens the result by Cardinal, Hoffmann, and Kusters (2015), that all planar graphs on $n \le 10$ vertices can be simultaneously drawn on particular \emph{$n$-universal} sets of $n$ points while there are no $n$-universal sets of size $n$ for $n \ge 15$. We also provide 49 planar 11-vertex graphs which cannot be simultaneously drawn on any set of 11 points. This, in fact, is another step towards a (negative) answer of the question, whether every two planar graphs can be drawn simultaneously -- a question raised by Brass, Cenek, Duncan, Efrat, Erten, Ismailescu, Kobourov, Lubiw, and Mitchell (2007).

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 rational $p>1$. In this paper, we consider the complexity of corresponding decision problems for related notions of fractional colourings for digraphs and graphs, including the star dichromatic number, the fractional dichromatic number and the circular vertex arboricity. We prove the following results:

-Deciding if the star dichromatic number of a digraph is at most $p$ is NP-complete for every rational $p>1$.

-Deciding if the fractional dichromatic number of a digraph is at most $p$ is NP-complete for every $p>1, p \neq 2$.

-Deciding if the circular vertex arboricity of a graph is at most $p$ is NP-complete for every rational $p>1$.

To show these results, different techniques are required in each case. In order to prove the first result, we relate the star dichromatic number to a new notion of homomorphisms between digraphs, called circular homomorphisms, which might be of independent interest. We provide a classification of the computational complexities of the corresponding homomorphism colouring problems similar to the one derived by Feder et al.~for acyclic homomorphisms.

We investigate which planar point sets allow simultaneous straight-line embeddings of all planar graphs on a fixed number of vertices. We first show that at least $(1.293-o(1))n$ points are required to find a straight-line drawing of each $n$-vertex planar graph (vertices are drawn as the given points); this improves the previous best constant $1.235$ by Kurowski (2004).

Our second main result is based on exhaustive computer search: We show that no set of 11 points exists, on which all planar 11-vertex graphs can be simultaneously drawn plane straight-line. This strengthens the result by Cardinal, Hoffmann, and Kusters (2015), that all planar graphs on $n \le 10$ vertices can be simultaneously drawn on particular \emph{$n$-universal} sets of $n$ points while there are no $n$-universal sets of size $n$ for $n \ge 15$. We also provide 49 planar 11-vertex graphs which cannot be simultaneously drawn on any set of 11 points. This, in fact, is another step towards a (negative) answer of the question, whether every two planar graphs can be drawn simultaneously -- a question raised by Brass, Cenek, Duncan, Efrat, Erten, Ismailescu, Kobourov, Lubiw, and Mitchell (2007).

Flip graphs are a ubiquitous class of graphs, which encode relations induced on a set of combinatorial objects by elementary, local changes. Skeletons of associahedra, for instance, are the graphs induced by quadrilateral flips in triangulations of a convex polygon. For some definition of a flip graph, a natural computational problem to consider is the flip distance: Given two objects, what is the minimum number of flips needed to transform one into the other?

We consider flip graphs on orientations of simple graphs, where flips consist of reversing the direction of some edges. More precisely, we consider so-called $\alpha$-orientations of a graph $G$, in which every vertex $v$ has a specified outdegree $\alpha(v)$, and a flip consists of reversing all edges of a directed cycle. We prove that deciding whether the flip distance between two $\alpha$-orientations of a planar graph $G$ is at most two is \NP-complete. This also holds in the special case of perfect matchings, where flips involve alternating cycles. This problem amounts to finding geodesics on the common base polytope of two partition matroids, or, alternatively, on an alcoved polytope. It therefore provides an interesting example of a flip distance question that is computationally intractable despite having a natural interpretation as a geodesic on a nicely structured combinatorial polytope.

We also consider the dual question of the flip distance between graph orientations in which every cycle has a specified number of forward edges, and a flip is the reversal of all edges in a minimal directed cut. In general, the problem remains hard. However, if we restrict to flips that only change sinks into sources, or vice-versa, then the problem can be solved in polynomial time. Here we exploit the fact that the flip graph is the cover graph of a distributive lattice. This generalizes a recent result from Zhang, Qian, and Zhang (Acta. Math. Sin.-English Ser., 2019).

  We introduce a new notion of circular colourings for digraphs. The idea of this quantity, called star dichromatic number $\vec{\chi}^\ast(D)$ of a digraph $D$, is to allow a finer subdivision of digraphs with the same dichromatic number into such which are ``easier'' or ``harder'' to colour by allowing fractional values. This is related to a coherent notion for the vertex arboricity of graphs introduced by Wang et al. and resembles the concept of the star chromatic number of graphs introduced by Vince in the framework of digraph colouring. After presenting basic properties of the new quantity, including range, simple classes of digraphs, general inequalities and its relation to integer counterparts as well as other concepts of fractional colouring, we compare our notion with the notion of circular colourings for digraphs introduced by Bokal et al. and point out similarities as well as differences in certain situations. As it turns out, the star dichromatic number shares all positive characteristics with the circular dichromatic number of Bokal et al., but has the advantage that it depends on the strong components of the digraph only, while the addition of a dominating source raises the circular dichromatic number to the ceiling. We conclude with a discussion of the case of planar digraphs and point out some open problems.

Planar graphs are known to have contact representations of various types. The most prominent example is Koebe’s ‘kissing coins theorem’. Its rediscovery by Thurston lead to effective versions of the Riemann Mapping Theorem and motivated Schramm’s Monster Packing Theorem. Monster Packing implies the existence of contact representations of planar triangulations where each vertex v is represented by a homothetic copy of some smooth strictly-convex prototype P_v. With this work we aim at computable approximations of Schramm representations. For fixed K approximate P_v by an equiangular K-gon Q_v with horizontal basis. From Schramm’s work it follows that the given triangulation also has a contact representation with homothetic copies of these K-gons. Our approach starts by guessing a K-contact-structure, i.e., the combinatorial structure of a contact representation. From the combinatorial data, we build a system of linear equations whose variables correspond to lengths of boundary segments of the K-gons. If the system has a non-negative solution, this yields the intended contact representation. If the solution of the system contains negative variables, these can be used as sign-posts indicating how to change the K-contact-structure for another try. In the case K = 3 the K-contact-structures are Schnyder woods, and in the case K = 4 they are transversal structures. As in these cases, for K ≥ 5 the K-contact-structures of a fixed graph are in bijection to certain integral flows, and can be viewed as elements of a distributive lattice. The procedure has been implemented, it computes the solution with few iterations. The experiments involved graphs with up to one hundered vertices. 

Representations of planar triangulations as contact graphs of a set of internally disjoint homothetic triangles or of a set of internally disjoint homothetic squares have received quite some attention in recent years. In this paper we investigate representations of planar triangulations as contact graphs of a set of internally disjoint homothetic pentagons. Surprisingly such a representation exists for every triangulation whose outer face is a 5-gon. We relate these representations to five color forests. These combinatorial structures resemble Schnyder woods and transversal structures, respectively. In particular there is a bijection to certain alpha-orientations and consequently a lattice structure on the set of five color forests of a given graph. This lattice structure plays a role in an algorithm that is supposed to compute a contact representation with pentagons for a given graph. Based on a five color forest the algorithm builds a system of linear equations and solves it, if the solution is non-negative, it encodes distances between corners of a pentagon representation. In this case the representation is constructed and the algorithm terminates. Otherwise negative variables guide a change of the five color forest and the procedure is restarted with the new five color forest. Similar algorithms have been proposed for contact representations with homothetic triangles and with squares.