Mathematics Problem Archive

Let M be a matroid on ground set S, and suppose that S can be partitioned into k bases. Is it true that there is a cyclic ordering of the elements of ...

What is the complexity of deciding kernel-perfectness in various classes of digraphs?...

In a soccer tournament of n teams, every pair of teams plays one match. The winner gets 3 points, the loser gets 0, while both teams receive 1 point i...

Let G=(V,E) be an undirected graph, and $r \in V$ a root node. G is called rooted (k,l)-connected if G-X is $(k-\vert X\vert)l$-edge-connected for any...

Let D=(V,A) be a digraph whose underlying graph is k-partition-connected, and let $r_0 \in V$ be a node of in-degree 0. Suppose that the in-degree of ...

Let G be a graph that is rigid in two-dimensional space. Can we determine in polynomial time the minimum number of edges whose deletion from G results...

Does there exist a value k so that in every k-arc-connected directed graph D=(V,A) and for every node $v\in V$, there is a spanning in-arborescence an...

Let f be a 2-polymatroid function on S that has a matroid representation $M=(S \times \{1,2\},r)$ with the following property: $|C\cap \{(e,1),(e,2)\}...

In a graph G=(V,E) with a root node r, two spanning trees $T_1$ and $T_2$ are called edge-independent if for any node x in V-r, the unique paths betwe...

Is it true that every graph G is equitably k-list-colourable for any $k \geq \Delta(G)+1$?...

Give an algorithm and/or a good characterization to decide if a red-blue edge-coloured bipartite graph contains a perfect matching with exactly k red ...

Let A be an $n \times n$ 0-1 matrix, and suppose that the facets of the polyhedron $P=\{x: A x \leq {\mathbf 1},\ x \leq {\mathbf 1}\}$ are coloured b...

In which classes of digraphs can we decide if a kernel exists and find one in polynomial time?...

Decide whether a graph is globally rigid in three-dimensional space....

Can we decide in polynomial time whether a given graph is rigid in 3-dimensional space?...

A spanning tree of a graph G is called $\epsilon$-thin if it contains at most an $\epsilon$ fraction of the edges of each cut. Is there a function $f:...

How does gonality change if each edge of the graph is subdivided $k$ times?...

An orientation of a hypergraph is a directed hypergraph obtained by choosing a single head-node in each hyperedge. We call a set of orientations of a ...

Is it true that if an undirected graph G with terminal set T is 2k-element-connected, then it has a k-element-connected orientation?...

Given a digraph D=(V+s,A) which is k-arc-connected in V, what is the maximum number of (disjoint) pairs of arcs, consisting of entering and leaving ar...

Let D=(V,A) be an acyclic digraph with designated root-nodes $r_1,...,r_k\in V$. Let $U_1,...,U_k$ be convex node sets with $r_i\in U_i$. Is it true t...

In a graph G=(V,E) with a root node r, two spanning trees $T_1$ and $T_2$ are called r-independent if for any node x in V-r, the unique paths between ...

For a digraph $D=(V,A)$, we call a nonempty $C\subseteq A$ a dicut if there is some $X\subseteq V$ such that no edge enters $X$ and $C$ consists of th...

Is it true that every smooth polytope has the integer decomposition property?...

Given some matroids on the same ground set $S$, a colouring of $S$ is called proper if each monochromatic set is independent in each matroid. Let $M_1...

We are given a hypergraph $G_0=(V,\mathcal{E}_0)$ of rank at most $k$ (where $k$ is fixed, not part of the input) and a symmetric function $r:V\times ...

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