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

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

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

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

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

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

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

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

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

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

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

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

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