Mathematics Problem Archive

Let D=(V,E) be a directed graph that is the union of two disjoint directed spanning trees. Can we characterize when does D have a directed spanning tr...

Given an undirected graph G=(V,E), find a maximum cardinality 2-matching containing no cycles of length 4 in polynomial time....

Let (G,<) be a preference system with ties where in every odd cycle there is a node that prefers its clockwise neighbour to its other neighbour, and t...

Given a graph G=(V,E), and weight and capacity functions $w,u: E \to {\mathbb R_+}$ defined on the edge set, is there a combinatorial, strongly polyno...

Given a bipartite graph G with edge weights, can we find in polynomial time a maximum weight k-element matching in G that can be extended to a perfect...

Let G=(V,E) be an undirected graph and let $(s_1,t_1), (s_2,t_2)$ be two node pairs. Give a combinatorial, polynomial-time algorithm to find edge-disj...

Can we find a minimum k-way cut in a capacitated hypergraph in polynomial time, if k is fixed?...

For a plane graph $G$, let $g(G)$ denote the length of the shortest face in $G$. For a (not necessarily proper) $k$-coloring of $V(G)$ we say that a f...

Is it true that if all vertices of a base polyhedron B are in $\{0,1,-1\}^n$ and $0 \in B$, then B has a vertex v such that -v is also a vertex?...

Any $2k$-edge-connected (possibly infinite) multigraph admits a $k$-edge-connected orientation....

Let $\mathcal{C}$ be a clutter on ground set V, and let $\mathcal{B}$ be its blocker. Is it true that $\mathcal{C}$ is nonideal if and only if there e...

Let G=(V,E) be a mixed graph with non-negative edge-lengths and let $s,t \in V$. Can we find in polynomial time an orientation where the sum of the le...

Given a digraph D=(V,A) and non-negative even-valued arc weights $w_a\ (a \in A)$, can we find in polynomial time a w-vertex cover $x$ of the underlyi...

Find a good characterization for undirected graphs having a strongly connected (more generally k-edge-connected) orientation so that the in-degree of ...

Let P be the set of partitions of a ground set S. We allow two operations on P: (1) splitting a class into two arbitrary classes and (2) joining two c...

Let G=(V,E) be a bipartite graph, and $c_1,\dots c_k$ positive reals whose sum is 1. Can E always be partitioned into k parts $E_1,\dots,E_k,$ so that...

For which classes of digraphs can we explicitly give a linear description of the convex hull of kernels?...

A quasi-kernel of a digraph $D$ is an independent vertex set $K$ sucht that every vertex is reachable from $K$ in $D$ by a path of length at most two....

Given k disjoint matchings in a bipartite graph, a rainbow matching is a matching that contains one edge from each of them. Is it true that any family...

Given a crossing negamodular function $R:2^V\to \mathbb{Z}$ such that $R(X)\ne 1$ for every $X\subseteq V$ and a hypergraph $G_0=(V,\mathcal{E}_0)$, f...

A graph G is said to be a Seymour graph if for any edge set F that satisfies $|C\cap F|\le |C\setminus F|$ for every circuit C of G, there exist $|F|$...

Given a directed graph whose arcs are coloured red and blue and integers r and b, can we decide in polynomial time whether the digraph has a cut with ...

Let $M$ be a matroid of rank n whose ground set S can be partitioned into n disjoint bases $B_1,\dots,B_n$. Is it true that $B_1,\dots,B_n$ always hav...

The rotor-routing halting problem asks the following: Given an initial chip-and-rotor configuration on a digraph, does the rotor-routing game eventual...

Given a digraph D=(V,A), two (not necessarily disjoint) subsets $S,T\subseteq V$ and a connectivity requirement k, develop a strongly polynomial time ...

Let G=(V,E) be an Eulerian graph with minimum degree at least 4, and let W be a closed Eulerian walk of G. Is it true that G has a cycle decomposition...

Let $M=(S,r)$ be a loopless matroid of rank k whose ground set can be partitioned into k bases. Is it true that no matter how we partition S into sets...

Let M be a matroid, and let A and B be two bases of M. A subset X of A and a subset Y of B, both of size k, form a serial symmetric exchange with resp...

Let $p_1$ and $p_2$ be integer skew-supermodular set functions on ground set S such that $\max\{p_1(X),p_2(X)\}\leq \min\{|X|,k\}$ for every $X \subse...

Is it true that if D=(V,A) is a digraph where every node has positive out-degree, then D has a quasi-kernel of size at most |V|/2?...

Let $G=(V,E)$ be an undirected graph, and $T \subseteq V$ a set of nodes of odd degree. When does an orientation $D$ of $G$ exist which is i) smooth (...

Devise combinatorial polynomial-time algorithms for the following two problems. Given a graph G, find a subgraph H with $O(n)$ edges such that $d_H(X)...

Let G=(V,E) be a graph with maximum degree $\Delta \geq 2$, and let M=(V,r) be a matroid that has $2 \Delta$ disjoint bases. Is it true that M has $2 ...

Let the graphs $G=(V,E)$ and $H$ be fixed. An edge set $F\subseteq E$ is called $H$-free if $(V,F)$ does not contain $H$ as a subgraph. We say that $F...

Is it true that if all the hyperedges of a hypergraph $H$ have size at most $k$ for some $k\in \mathbb{N}$, then $H$ admits a strongly maximal matchin...

Is it true that if the hypergraph $H$ has no isolated vertices and all of its hyperedges are finite, then $H$ admits a strongly minimal edge cover?...

For a loopless matroid $M=(S,r)$, let $\Delta(M)=\max_{X\subseteq S} |X|/r(X)$. Let $M_1=(S,r_1)$ and $M_2=(S,r_2)$ be two arbitrary loopless matroids...

$\rm{gon}(G) \leq \frac{|E(G)|-|V(G)|}{2} + 2$, where $\rm{gon}(G)$ the denotes the divisorial gonality of graph $G$....

Let G=(S,T;E) be a bipartite graph, with weights $w:E \to [0,1]$. A proper weighted edge colouring is a colouring of the edges such that at each verte...

When can we characterize hypergraphs that have an orientation satisfying a prescribed symmetric local edge-connectivity requirement? Special case: can...

Erdős: How many colors is it necessary to use so that, if you paint every single point of the two-dimensional plane some color, no two points which ar...

Graham: A set of points S is Euclidean Ramsey if, for every k, there exists an N so that every k-coloring of Euclidean N-space contains a monochromati...

Graham: For every non-equilateral triangle T, show that it is possible to color the plane with three colors so that there is no monochromatic (congrue...

Pach : Suppose a geometric graph has no pairwise k-crossing lines. That is, no k edges all cross each other. Must the graph have O_(k)(n) edges?...

: Suppose we begin with a set of points S in the plane. Let T(S) be the set of points one gets by taking all lines through pairs of points in S, and t...

Kalai : Suppose H is a linear 3-uniform hypergraph, i.e., a subset of the set of all triples of n points with the property that no two edges intersect...

Solymosi : Suppose a family V of n points are chosen in R^(3) and L is a collection of lines so that every triangle spanned by three points of V is pi...

Conway : Does every thrackle have average degree at most 2? A thrackle is a drawing of a graph in the plane so that every two edges share exactly one ...

What is the minimum number of n-simplexes needed to triangulate the n-cube? See this....

How many congruent regular tetrahedra can touch at a point? Easy to show it's at least 20, and at most 22. Apparently, this has been open a long time....