7 citations · 44 across the 35 of their papers we have counts for
15 papers · 1 filter
Inapproximability of shortest paths on perfect matching polytopes
Jean Cardinal, Raphael Steiner
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 , there is no polynom…
Subdigraphs of prescribed size and outdegree
Raphael Steiner
In 2006, Noga Alon raised the following open problem: Does there exist an absolute constant such that every -vertex digraph with minimum out-degree at least contains…
Strengthening Hadwiger's conjecture for - and -chromatic graphs
Anders Martinsson, Raphael Steiner
Hadwiger's famous coloring conjecture states that every -chromatic graph contains a -minor. Holroyd [Bull. London Math. Soc. 29, (1997), pp. 139--144] conjectured the follo…
Subdivisions with congruence constraints in digraphs of large chromatic number
Raphael Steiner
We prove that for every digraph and every assignment of pairs of integers to its arcs there exists an integer such that every digraph with dich…
Small diameters and generators for arithmetic lattices in and certain Ramanujan graphs
Raphael S. Steiner
We show that arithmetic lattices in , stemming from the proper units of an Eichler order in an indefinite quaternion algebra over , admit a…
Theta functions, fourth moments of eigenforms, and the sup-norm problem II
Ilya Khayutin, Paul D. Nelson, Raphael S. Steiner
For an -normalized holomorphic newform of weight on a hyperbolic surface of volume attached to an Eichler order of squarefree level in an indefinite quaternion alg…
Exact Matching: Correct Parity and FPT Parameterized by Independence Number
Nicolas {El Maalouly}, Raphael Steiner, Lasse Wulf
Given an integer 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…
Coloring hypergraphs with excluded minors
Raphael Steiner
Hadwiger's conjecture, among the most famous open problems in graph theory, states that every graph that does not contain as a minor is properly -colorable. The purpos…
Coloring circle arrangements: New -chromatic planar graphs
Man-Kwun Chiu, Stefan Felsner, Manfred Scheucher +3
Felsner, Hurtado, Noy and Streinu (2000) conjectured that arrangement graphs of simple great-circle arrangements have chromatic number at most . Motivated by this conjecture, we…
Cycle lengths modulo in expanders
Anders Martinsson, Raphael Steiner
Given a constant , an -vertex graph is called an -expander if every set of at most vertices in has an external neighborhood of size at least . Addres…
Improved bound for improper colorings of graphs with no odd clique minor
Raphael Steiner
Strengthening Hadwiger's conjecture, Gerards and Seymour conjectured in 1995 that every graph with no odd -minor is properly -colorable, this is known as the Odd Hadwig…
Heroes in orientations of chordal graphs
Pierre Aboulker, Guillaume Aubian, Raphael Steiner
We characterize all digraphs such that orientations of chordal graphs with no induced copy of have bounded dichromatic number.
Exact Matching in Graphs of Bounded Independence Number
Nicolas El Maalouly, Raphael Steiner
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 . The task is…
Matching Theory and Barnette's Conjecture
Maximilian Gorsky, Raphael Steiner, Sebastian Wiederrecht
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. Th…
Disproof of a Conjecture by Woodall
Raphael Steiner
In 2001, Woodall conjectured that for every pair of integers , all graphs without a -minor are -choosable. In this note we refute this conjecture in a…