Mathematics Problem Archive

Every finite simple graph on at least 3 vertices is uniquely determined by its vertex-deleted subgraphs....

Every tree can be gracefully labeled: vertices can be assigned distinct labels from $\{0, 1, \ldots, |E|\}$ such that edge labels (absolute difference...

For any $k$-chromatic graph, can its $k$-colorings be transformed into each other by recoloring one vertex at a time, staying within $k$ colors, in po...

Can every graph be totally colored with at most $\Delta + 2$ colors, where $\Delta$ is the maximum degree?...

Does there exist a graph where the dominating number equals the eternal dominating number and both are less than the clique covering number?...

If Alice has a winning strategy for the vertex coloring game with k colors, does she have one for k+1 colors?...

What is the maximum chromatic number of biplanar graphs?...

Does every thrackle have at most as many edges as vertices?...

What is the maximum pathwidth of an n-vertex cubic graph?...

What is the longest induced path in an n-dimensional hypercube graph?...

Are there graphs on n vertices requiring more than floor(n/2) copies of each letter for word-representation?...

Classify graphs with representation number exactly 3....

Among bipartite graphs, do crown graphs require the longest word-representants?...

If every edge has imbalance ≥1, is the multiset of edge imbalances always graphic?...

Is the bondage number of a graph always ≤ 3Δ/2, where Δ is the maximum degree?...

The deck of a graph $G$ is the multiset consisting of all unlabelled subgraphs obtained from $G$ by deleting a vertex in all possible ways (counted ac...

Conjecture For every graph with no bridge, there is a list of cycles so that every edge is contained in exactly two....

Conjecture If $G$ is a bridgeless cubic graph, then there exist 6 perfect matchings $M_1,\ldots,M_6$ of $G$ with the property that every edge of $G$ i...

Conjecture Every bridgeless graph has a nowhere-zero 5-flow....

Conjecture Every simple digraph of order $n$ with minimum outdegree at least $r$ has a cycle with length at most $\lceil n/r\rceil$...

Can the sequence of metric balls in an infinite Cayley graph form a family of expanders?...

For a graph sequence $(G_n)$ define $e((G_n))=\liminf |E(G_n)|/|V(G_n)|$, and define its combinatorial cost as the infimum of $e((H_n))$ over graph se...

Compactness implies that for every $\varepsilon>0$ there is $K>0$ such that every finite graph can be approximated within error $\varepsilon$ by a fin...

Which probability measures can occur as eigenvalue distributions of finite $d$-regular graphs? Find natural restrictions....

Do uniformly random $d$-regular graphs converge, in local-global convergence, to the weak closure of independent identically distributed processes?...

Is the i.i.d. action of the free group $F_2$ a local-global limit of finite actions of $F_2$?...

Can every ergodic unimodular random network that is almost surely an infinite tree be obtained as the limit of an expander family?...

Let $G$ be an infinite vertex-transitive graph, let $A$ be a finite vertex set, let $b$ be a vertex, and let $\partial A$ be the set of vertices at di...

Define the first $L^2$ Betti number of a vertex-transitive graph $G$ from the expected degree of a free spanning forest. Do $G$ and its square $G^2$ h...

Does every infinite Cayley graph, or every infinite vertex-transitive graph, have a spanning tree without leaves?...

In every infinite Cayley graph, does the density of dead ends tend to zero?...

Are factors of i.i.d. on the $3$-regular tree closed in the weak topology? In particular, is the weak limit of majority functions on $n$-balls a facto...

For every $k>1$, does there exist $C(k)<1$ such that the return probability of every transient $k$-regular Cayley graph is at most $C(k)$?...

Let $(G_n)$ and $(H_n)$ converge to the same graph limit, and let $(T_n)$ be a convergent sequence with each $T_n$ a spanning tree of $G_n$. Do there ...

Let $G$ be a bounded-degree expander, or strongly ergodic, graphing that can be properly colored by $C$ colors with arbitrarily small error. Can it be...

Is there a polynomial time algorithm that is able to find the largest clique of $G$ (with high probability) for $\omega \ll \sqrt{n}$ ? For example, f...

Does every simple graph with maximum vertex degree $\Delta \leq 6$ have a 3D orthogonal point-drawing with no more than two bends per edge? A 3D ortho...

Babai's problem: which groups are Babai invariant groups?...

Given $n\in\mathbb{N}$, can a prime $p>n$ be found in deterministic polynomial time?...

Given coprime $a,n\in\mathbb{N}$, can a prime $p\equiv a\pmod n$ be found in deterministic polynomial time?...

Is complete integer factorization $C_5$ in deterministic polynomial time $P$?...

Is complete integer factorization $C_5$ in randomized polynomial time $R$?...

Does there exist a set $S\subset\mathbb{N}$ of positive lower asymptotic density for which complete factorization of every input $n\in S$ is in determ...

Given $n$, can one find $r,s\in\mathbb{N}$ with $n=r^2s$ and $s$ squarefree in deterministic polynomial time?...

Is complete integer factorization randomized polynomial-time reducible to computation of the squarefree part?...

Can $\omega(n)$, the number of distinct prime factors of $n$, be computed in deterministic polynomial time?...

Can one decide in deterministic polynomial time whether a coprime integer $a$ is a square modulo a composite $n$?...

Is complete integer factorization randomized polynomial-time reducible to deciding quadratic residuosity modulo a composite?...

Given a prime $p$, can a quadratic nonresidue modulo $p$ be found in deterministic polynomial time?...

Given a sign vector $\varepsilon\in\{-1,1\}^k$, can the least prime $p$ satisfying $(p_i/p)=\varepsilon_i$ for every $i\le k$ be found in deterministi...