Grunbaum's Conjecture
Conjecture If $G$ is a simple loopless triangulation of an orientable surface, then the dual of $G$ is 3-edge-colorable....
5-local-tensions
Conjecture There exists a fixed constant $c$ (probably $c=4$ suffices) so that every embedded (loopless) graph with edge-width $\ge c$ has a 5-local-t...
Degenerate colorings of planar graphs
A graph $G$ is $k$-degenerate if every subgraph of $G$ has a vertex of degree $\le k$. Conjecture Every simple planar graph has a 5-coloring so that ...
3-Colourability of Arrangements of Great Circles
Consider a set $S$ of great circles on a sphere with no three circles meeting at a point. The arrangement graph of $S$ has a vertex for each intersect...
The Crossing Number of the Complete Graph
The crossing number $cr(G)$ of $G$ is the minimum number of crossings in all drawings of $G$ in the plane. Conjecture $\displaystyle cr(K_n) = \frac ...
The Crossing Number of the Complete Bipartite Graph
The crossing number $cr(G)$ of $G$ is the minimum number of crossings in all drawings of $G$ in the plane. Conjecture $\displaystyle cr(K_{m,n}) = \f...
The Crossing Number of the Hypercube
The crossing number $cr(G)$ of $G$ is the minimum number of crossings in all drawings of $G$ in the plane. The $d$-dimensional (hyper)cube $Q_d$ is t...
Drawing disconnected graphs on surfaces
Conjecture Let $G$ be the disjoint union of the graphs $G_1$ and $G_2$ and let $\Sigma$ be a surface. Is it true that every optimal drawing of $G$ on ...
Crossing sequences
Conjecture Let $(a_0,a_1,a_2,\ldots,0)$ be a sequence of nonnegative integers which strictly decreases until $0$. Then there exists a graph that be d...
Crossing numbers and coloring
We let $cr(G)$ denote the crossing number of a graph $G$. Conjecture Every graph $G$ with $\chi(G) \ge t$ satisfies $cr(G) \ge cr(K_t)$....
Are different notions of the crossing number the same?
Problem Does the following equality hold for every graph $G$? $$ \text{pair-cr}(G) = \text{cr}(G) $$ The crossing number $\text{cr}(G)$ of a graph $G...
Universal point sets for planar graphs
We say that a set $P \subseteq {\mathbb R}^2$ is $n$-universal if every $n$ vertex planar graph can be drawn in the plane so that each vertex maps to ...
Linear Hypergraphs with Dimension 3
Conjecture Any linear hypergraph with incidence poset of dimension at most 3 is the intersection hypergraph of a family of triangles and segments in t...
Consecutive non-orientable embedding obstructions
Conjecture Is there a graph $G$ that is a minor-minimal obstruction for two non-orientable surfaces?...
What is the largest graph of positive curvature?
Problem What is the largest connected planar graph of minimum degree 3 which has everywhere positive combinatorial curvature, but is not a prism or an...
Growth of finitely presented groups
Problem Does there exist a finitely presented group of intermediate growth?...
Subgroup formed by elements of order dividing n
Conjecture Suppose $G$ is a finite group, and $n$ is a positive integer dividing $|G|$. Suppose that $G$ has exactly $n$ solutions to $x^{n} = 1$. Do...
Burnside problem
Conjecture If a group has $r$ generators and exponent $n$, is it necessarily finite?...
Inverse Galois Problem
Conjecture Every finite group is the Galois group of some finite algebraic extension of $\mathbb Q$....
Which lattices occur as intervals in subgroup lattices of finite groups?
Conjecture There exists a finite lattice that is not an interval in the subgroup lattice of a finite group....
F_d versus F_{d+1}
Problem Find a constant $k$ such that for any $d$ there is a sequence of tautologies of depth $k$ that have polynomial (or quasi-polynomial) size proo...
Tarski's exponential function problem
Conjecture Is the theory of the real numbers with the exponential function decidable?...
Termination of the sixth Goodstein Sequence
Question How many steps does it take the sixth Goodstein sequence to terminate?...
Fixed-point logic with counting
Question Can either of the following be expressed in fixed-point logic plus counting: - Given a graph, does it have a perfect matching, i.e., a set $...
Order-invariant queries
Question - Does ${<}\text{-invariant\:FO} = \text{FO}$ hold over graphs of bounded tree-width? - Is ${<}\text{-invariant\:FO}$ included in $\text{MSO...
Monadic second-order logic with cardinality predicates
The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the following atomic for...
Blatter-Specker Theorem for ternary relations
Let $C$ be a class of finite relational structures. We denote by $f_C(n)$ the number of structures in $C$ over the labeled set $\{0, \dots, n-1 \}$. F...
MSO alternation hierarchy over pictures
Question Is the MSO-alternation hierarchy strict for pictures that are balanced, in the sense that the width and the length are polynomially (or linea...
Finite entailment of Positive Horn logic
Question Positive Horn logic (pH) is the fragment of FO involving exactly $\exists, \forall, \wedge, =$. Does the fragment $pH \wedge \neg pH$ have th...
Vertex Cover Integrality Gap
Conjecture For every $\varepsilon > 0$ there is $\delta > 0$ such that, for every large $n$, there are $n$-vertex graphs $G$ and $H$ such that $G \equ...
Lonely runner conjecture
Conjecture Suppose $k$ runners having distinct constant speeds start at a common point and run laps on a circular track with circumference 1. Then for...
MacEachen Conjecture
Conjecture Every odd prime number must either be adjacent to, or a prime distance away from a primorial or primorial product....
Chowla's cosine problem
Problem Let $A \subseteq {\mathbb N}$ be a set of $n$ positive integers and set $$ m(A) = - \min_x \sum_{a \in A} \cos(ax). $$ What is $m(n) = \min_A...
Quartic rationally derived polynomials
Call a polynomial $p \in {\mathbb Q}[x]$ rationally derived if all roots of $p$ and the nonzero derivatives of $p$ are rational. Conjecture There doe...
A discrete iteration related to Pierce expansions
Conjecture Let $a > b > 0$ be integers. Set $b_1 = b$ and $b_{i+1} = {a \bmod {b_i}}$ for $i \geq 0$. Eventually we have $b_{n+1} = 0$; put $P(a,b) = ...
Algebraic independence of pi and e
Conjecture $\pi$ and $e$ are algebraically independent...
Odd perfect numbers
Conjecture There is no odd perfect number....
Diophantine quintuple conjecture
Definition A set of m positive integers $\{a_1, a_2, \dots, a_m\}$ is called a Diophantine $m$-tuple if $a_i\cdot a_j + 1$ is a perfect square for all...
Twin prime conjecture
Conjecture There exist infinitely many positive integers $n$ so that both $n$ and $n+2$ are prime....
Polignac's Conjecture
Conjecture Polignac's Conjecture: For any positive even number n, there are infinitely many prime gaps of size n. In other words: There are infinitely...
Special Primes
Conjecture Let $p$ be a prime natural number. Find all primes $q\equiv1\left(\mathrm{mod}\: p\right)$, such that $2^{\frac{\left(q-1\right)}{p}}\equiv...
Primitive pythagorean n-tuple tree
Conjecture Find linear transformation construction of primitive pythagorean n-tuple tree!...
3 is a primitive root modulo primes of the form 16 q^4 + 1, where q>3 is prime
Conjecture $3~$ is a primitive root modulo $~p$ for all primes $~p=16\cdot q^4+1$, where $~q>3$ is prime....
Erdős–Straus conjecture
Conjecture For all $n > 2$, there exist positive integers $x$, $y$, $z$ such that $$1/x + 1/y + 1/z = 4/n$$....
Lucas Numbers Modulo m
Conjecture The sequence {L(n) mod m}, where L(n) are the Lucas numbers, contains a complete residue system modulo m if and only if m is one of the fol...
Sum of prime and semiprime conjecture
Conjecture Every even number greater than $10$ can be represented as the sum of an odd prime number and an odd semiprime....
Giuga's Conjecture on Primality
Conjecture $p$ is a prime iff $~\displaystyle \sum_{i=1}^{p-1} i^{p-1} \equiv -1 \pmod p$...
Alexa's Conjecture on Primality
Definition Let $r_i$ be the unique integer (with respect to a fixed $p\in\mathbb{N}$ ) such that $$(2i+1)^{p-1} \equiv r_i \pmod p ~~\text{ and } ~ 0...
Birch & Swinnerton-Dyer conjecture
Conjecture Let $E/K$ be an elliptic curve over a number field $K$. Then the order of the zeros of its $L$-function, $L(E, s)$, at $s = 1$ is the Morde...
The Erdos-Turan conjecture on additive bases
Let $B \subseteq {\mathbb N}$. The representation function $r_B: {\mathbb N} \rightarrow {\mathbb N}$ for $B$ is given by the rule $r_B(k) = \#\{ (i,j...