Mathematics Problem Archive

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

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

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