Mathematics Problem Archive

What is the minimum number of colors needed to color the points of the plane such that no two points at distance 1 have the same color?...

What is the exact value of $R(5,5)$, the smallest number $n$ such that any 2-coloring of the edges of $K_n$ contains a monochromatic $K_5$?...

For any $n$ runners on a circular track with distinct constant speeds, each runner is "lonely" (distance at least $1/n$ from all others) at some time....

For every finite union-closed family of sets (other than the empty family), there exists an element that belongs to at least half of the sets....

Does there exist a finite upper bound on how many times a number (other than 1) can appear in Pascal's triangle?...

What is the maximum number of points in an $n \times n$ grid with no three collinear?...

Given the width of a tic-tac-toe board, what is the smallest dimension guaranteeing X has a winning strategy?...

What is the outcome of a perfectly played game of chess?...

What is the perfect value of komi (compensation points) in Go?...

Are the nim-sequences of all finite octal games eventually periodic?...

Is the nim-sequence of Grundy's game eventually periodic?...

What is the optimal strategy for two agents to meet on a network without communication?...

Does every non-total finite poset have two elements x,y with P(x before y in random linear extension) ∈ [1/3, 2/3]?...

Let $R(k,k)$ denote the $k^{th}$ diagonal Ramsey number. Conjecture $\lim_{k \rightarrow \infty} R(k,k) ^{\frac{1}{k}}$ exists. Problem Determine th...

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