Mathematics Problem Archive

The Betti poset of a monomial ideal $I$ determines the Stanley projective dimension of $S/I$ and $I$. More precisely, if $I\subseteq S$ and $I'\subset...

Given a graph $G(V,E)$, find a minimum cardinality set $S \subset V$ of nodes such that adding a complete graph on $S$ renders the graph $G+K_S$ globa...

Problem 1. Given an undirected graph $\displaystyle G=(V,E)$ and $\displaystyle s,t\in V,\;\; k\in N$, decide whether the graph has an acyclic orienta...

Problem 1. Find a good characterization for undirected graphs having an acyclic orientation so that the in-degree of every node is even. Problem 2. Fi...

Is it true that every t-perfect graph is strongly t-perfect?...

Are there deletion-contraction formulas for the polymatroid Tutte polynomial?...

Let D be a digraph without loops and k a positive integer. For a partition $\Pi$ of V(D) into directed paths (a path partition) let $|\Pi|_k=\sum_{P \...

Let $B=\{b_1,b_2,\ldots ,b_k\}\subset\{0,1,\ldots ,n-1\}$, and let $B_i=\{b_1+i, b_2+i,\ldots, b_k+i\}$ where addition is modulo n. That is, ${\mathca...

Let M be a matroid on ground set V, let H=(V,E) be a hypergraph with maximum degree $\Delta$, let c(v) be the cost of node v, and let $l(e) \leq u(e)$...

Let D=(V,A) be a digraph with arc-capacities $c : A \to \mathbb{N}$ and a root node $r_0\in V$. A k-arborescence is the arc-disjoint union of k spanni...

Let G=(A,B;E) be a bipartite graph, and $w:E \to \{1,-1\}$ a conservative weighting. Can we determine in polynomial time the maximum number of positiv...

Is every t-perfect graph 4-colourable?...

A hypergraph $H=(V,E)$ has the Kőnig-property if there is a set $\mathcal{D}\subseteq E$ of pairwise disjoint hyperedges such that there is a vertex c...

If G is an undirected graph with even degrees then call two closed Eulerian walks compatible if no pair of incident edges occurs consecutively in both...

Is there a polynomial algorithm for computing a $v_0$-reduced divisor equivalent to a given divisor of an undirected multigraph?...

Let $G$ be an undirected graph. What is the complexity of computing the rotor-router action of the sandpile group of $G$ on the spanning trees of $G$?...

Is the chip-firing reachability problem co-NP-hard for general digraphs?...

Is the chip-firing halting problem in P for Eulerian digraphs with multiple edges?...

Is it true that the chip-firing halting problem for simple digraphs is NP-complete?...

Is it true that a clutter has the MFMC property if and only if it has the packing property?...

Find a constructive characterization of k-dumpy graphs....

Given a crossing supermodular function $p:2^V\to \mathbb{Z}$ satisfying $p(\emptyset)=p(V)=0$, what is the minimum number of edges of an undirected gr...

Given a crossing supermodular function $p:2^V\to \mathbb{Z}$ satisfying $p(\emptyset)=p(V)=0$, what is the minimum number of pairwise non-parallel arc...

Given a symmetric crossing supermodular function $p:2^V\to \mathbb{R}$ and positive integers $n_1,n_2,\dots,n_k$, does there exist a hypergraph H=(V,E...

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