Source author record

Raphael Steiner

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Computational Geometry Data Structures and Algorithms

Catalog footprint

Research overview

20works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2024arXiv

Hadwiger's conjecture and topological bounds

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š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án [European Journal of Combinatorics, 31(8), 2110--2119 (2010)]. We also prove that if for a graph $G$ the Dol'nikov-Kříž 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á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.

preprint2023arXiv

Twin-width of sparse random graphs

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ős-Renyi and regular random graphs, complementing the bounds in the denser regime due to Ahn, Chakraborti, Hendrey, Kim and Oum.

preprint2022arXiv

Coloring circle arrangements: New $4$ -chromatic planar graphs

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 $χ_f(\mathcal{A})$ of the arrangement graph is bounded from above by $χ_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ündgen, Li, and Thomassen (2019).

preprint2022arXiv

Coloring Drawings of Graphs

We consider cell colorings of drawings of graphs in the plane. Given a multi-graph $G$ together with a drawing $Γ(G)$ in the plane with only finitely many crossings, we define a cell $k$ -coloring of $Γ(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.

preprint2022arXiv

Colorings of oriented planar graphs avoiding a monochromatic subgraph

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 $Δ(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 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 acyclic and planar input digraph $D$ admits an $F$ -free $3$ -coloring.

preprint2022arXiv

Cycle lengths modulo $k$ in expanders

Given a constant $α>0$ , an $n$ -vertex graph is called an $α$ -expander if every set $X$ of at most $n/2$ vertices in $G$ has an external neighborhood of size at least $α|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 $α>\frac{1}{p-1}$ every sufficiently large $α$ -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 $α<\frac{c}{p-1}$ , there exist arbitrarily large $α$ -expanding graphs with no cycles of length $r$ modulo $k$ , for some $r \in \{0,\ldots,k-1\}$ .

preprint2022arXiv

Disproof of a Conjecture by Woodall

In 2001, 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)$ .

preprint2022arXiv

Exact Matching in Graphs of Bounded Independence Number

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 $\textbf{NP}$ -complete. Later however, Mulmuley et al.~presented a randomized polynomial time algorithm for EM, which puts EM in $\textbf{RP}$ . Given that to decide whether or not $\textbf{RP}=\textbf{P}$ represents a big open challenge in complexity theory, this makes it unlikely for EM to be $\textbf{NP}$ -complete, and in fact indicates the possibility of a deterministic polynomial time algorithm. EM remains one of the few natural combinatorial problems in $\textbf{RP}$ which are not known to be contained in $\textbf{P}$ , making it an interesting instance for testing the hypothesis $\textbf{RP}=\textbf{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 finally 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.

preprint2022arXiv

Improved bound for improper colorings of graphs with no odd clique minor

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.

preprint2022arXiv

Matching Theory and Barnette's Conjecture

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.

preprint2022arXiv

Strengthening Hadwiger's conjecture for $4$ - and $5$ -chromatic graphs

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

preprint2022arXiv

Subdivisions with congruence constraints in digraphs of large chromatic number

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 at least $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 for undirected graphs, and at the same time yields a novel short proof of his result.

preprint2021arXiv

Complete minors in digraphs with given dichromatic number

The dichromatic number $\vecχ(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 directed graph minors in digraphs with given dichromatic number. In this short note we improve several of the existing bounds and prove almost linear bounds by reducing the problem to a recent result of Postle on Hadwiger's conjecture.

preprint2021arXiv

On coloring digraphs with forbidden induced subgraphs

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árfás-Sumner conjecture to directed graphs by Aboulker et al.

preprint2021arXiv

Zero sum cycles in complete digraphs

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 of order $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 bound 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 also obtain that every $K_{16q}$ -minor contains a cycle of length divisible by $q$ for every integer $q \ge 2$ , which improves a result by Alon and Krivelevich.

preprint2020arXiv

A Note on Coloring Digraphs of Large Girth

The digirth of a digraph is the length of a shortest directed cycle. The dichromatic number $\vecχ(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χ(D) \le \left\lceil\fracΔ{4}\right\rceil+1$ for every digraph $D$ of digirth at least $3$ and maximum degree $Δ$ . The best known partial result by Golowich shows that $\vecχ(D) \le \frac{2}{5}Δ+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 $Δ$ , then $\vecχ(D) \le (\frac{1}{3}+\frac{1}{3g}) Δ+ O_g(1)$ . This improves the bound of Golowich for digraphs without directed cycles of length at most $10$ .

preprint2020arXiv

Dichromatic number and forced subdivisions

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χ}(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χ}(F)=v(F)$ . This settles a conjecture of Aboulker, Cohen, Havet, Lochet, Moura and Thomassé. 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χ}(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.

preprint2020arXiv

On the Average Complexity of the $k$ -Level

Let ${\cal L}$ be an arrangement of $n$ lines in the Euclidean plane. The \emph{ $k$ -level} of ${\cal L}$ consists of all vertices $v$ of the arrangement which have exactly $k$ lines of ${\cal L}$ 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 \emph{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 $\mathbb{S}^d$ which are orthogonal to a set of random points on $\mathbb{S}^d$ . In this model, we prove that the expected complexity of the $k$ -level is of order $Θ((k+1)^{d-1})$ .

preprint2020arXiv

Oriented cycles in digraphs of large outdegree

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

preprint2020arXiv

Pentagon contact representations

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Raphael Steiner

Research overview

Is this your work?

20 publications

Hadwiger's conjecture and topological bounds

Twin-width of sparse random graphs

Coloring circle arrangements: New $4$ -chromatic planar graphs

Coloring Drawings of Graphs

Colorings of oriented planar graphs avoiding a monochromatic subgraph

Cycle lengths modulo $k$ in expanders

Disproof of a Conjecture by Woodall

Exact Matching in Graphs of Bounded Independence Number

Improved bound for improper colorings of graphs with no odd clique minor

Matching Theory and Barnette's Conjecture

Strengthening Hadwiger's conjecture for $4$ - and $5$ -chromatic graphs

Subdivisions with congruence constraints in digraphs of large chromatic number

Complete minors in digraphs with given dichromatic number

On coloring digraphs with forbidden induced subgraphs

Zero sum cycles in complete digraphs

A Note on Coloring Digraphs of Large Girth

Dichromatic number and forced subdivisions

On the Average Complexity of the $k$ -Level

Oriented cycles in digraphs of large outdegree

Pentagon contact representations

See the researcher in context

Building this map preview

Raphael Steiner

Research overview

Is this your work?

20 publications

Hadwiger's conjecture and topological bounds

Twin-width of sparse random graphs

Coloring circle arrangements: New 444-chromatic planar graphs

Coloring Drawings of Graphs

Colorings of oriented planar graphs avoiding a monochromatic subgraph

Cycle lengths modulo kkk in expanders

Disproof of a Conjecture by Woodall

Exact Matching in Graphs of Bounded Independence Number

Improved bound for improper colorings of graphs with no odd clique minor

Matching Theory and Barnette's Conjecture

Strengthening Hadwiger's conjecture for 444- and 555-chromatic graphs

Subdivisions with congruence constraints in digraphs of large chromatic number

Complete minors in digraphs with given dichromatic number

On coloring digraphs with forbidden induced subgraphs

Zero sum cycles in complete digraphs

A Note on Coloring Digraphs of Large Girth

Dichromatic number and forced subdivisions

On the Average Complexity of the kkk-Level

Oriented cycles in digraphs of large outdegree

Pentagon contact representations

See the researcher in context

Building this map preview

Coloring circle arrangements: New $4$ -chromatic planar graphs

Cycle lengths modulo $k$ in expanders

Strengthening Hadwiger's conjecture for $4$ - and $5$ -chromatic graphs

On the Average Complexity of the $k$ -Level