Recent Activity

Stable set meeting all longest directed paths. ★★

Author(s): Laborde; Payan; Xuong N.H.

\begin{conjecture} Every digraph has a stable set meeting all longest directed paths \end{conjecture}


Ádám's Conjecture ★★★

Author(s): Ádám

\begin{conjecture} Every digraph with at least one directed cycle has an arc whose reversal reduces the number of directed cycles. \end{conjecture}


Caccetta-Häggkvist Conjecture ★★★★

Author(s): Caccetta; Häggkvist

\begin{conjecture} Every simple digraph of order $n$ with minimum outdegree at least $r$ has a cycle with length at most $\lceil n/r\rceil$ \end{conjecture}


Directed path of length twice the minimum outdegree ★★★

Author(s): Thomassé

\begin{conjecture} Every oriented graph with minimum outdegree $k$ contains a directed path of length $2k$. \end{conjecture}


Antidirected trees in digraphs ★★

Author(s): Addario-Berry; Havet; Linhares Sales; Reed; Thomassé

An antidirected tree is an orientation of a tree in which every vertex has either indegree 0 or outdergree 0.

\begin{conjecture} Let $D$ be a digraph. If $|A(D)| > (k-2) |V(D)|$, then $D$ contains every antidirected tree of order $k$. \end{conjecture}


Decomposing an even tournament in directed paths. ★★★

Author(s): Alspach; Mason; Pullman

\begin{conjecture} Every tournament $D$ on an even number of vertices can be decomposed into $\sum_{v\in V}\max\{0,d^+(v)-d^-(v)\}$ directed paths. \end{conjecture}


Oriented trees in n-chromatic digraphs ★★★

Author(s): Burr

\begin{conjecture} Every digraph with chromatic number at least $2k-2$ contains every oriented tree of order $k$ as a subdigraph. \end{conjecture}


Discrete Logarithm Problem ★★★


If $p$ is prime and $g,h \in {\mathbb Z}_p^*$, we write $\log_g(h) = n$ if $n \in {\mathbb Z}$ satisfies $g^n = h$. The problem of finding such an integer $n$ for a given $g,h \in {\mathbb Z}^*_p$ (with $g \neq 1$) is the \emph{Discrete Log Problem}.

\begin{conjecture} There does not exist a polynomial time algorithm to solve the Discrete Log Problem. \end{conjecture}

Keywords: discrete log; NP

Good Edge Labelings ★★

Author(s): Araújo; Cohen; Giroire; Havet

\begin{question} What is the maximum edge density of a graph which has a good edge labeling? \end{question}

We say that a graph is \emph{good-edge-labeling critical}, if it has no good edge labeling, but every proper subgraph has a good edge labeling.

\begin{conjecture} For every $c<4$, there is only a finite number of good-edge-labeling critical graphs with average degree less than $c$. \end{conjecture}

Keywords: good edge labeling, edge labeling

Transversal achievement game on a square grid ★★

Author(s): Erickson

\begin{problem} Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an $n \times n$ grid. The first player (if any) to occupy a set of $n$ cells having no two cells in the same row or column is the winner. What is the outcome of the game given optimal play? \end{problem}

Keywords: game

Special Primes

Author(s): George BALAN

\begin{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}}\equiv1\left(\mathrm{mod}\: q\right)$. % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}


Three-chromatic (0,2)-graphs ★★

Author(s): Payan

\begin{question} Are there any (0,2)-graphs with chromatic number exactly three? \end{question}


Choice Number of k-Chromatic Graphs of Bounded Order ★★

Author(s): Noel

\begin{conjecture} If $G$ is a $k$-chromatic graph on at most $mk$ vertices, then $\text{ch}(G)\leq \text{ch}(K_{m*k})$. \end{conjecture}

Keywords: choosability; complete multipartite graph; list coloring

The Riemann Hypothesis ★★★★

Author(s): Riemann

The zeroes of the Riemann zeta function that are inside the Critical Strip (i.e. the vertical strip of the complex plane where the real part of the complex variable is in ]0;1[), are actually located on the Critical line ( the vertical line of the complex plane with real part equal to 1/2)

Keywords: Millenium Problems; zeta

Euler-Mascheroni constant ★★★


\begin{question} Is Euler-Mascheroni constant an transcendental number? \end{question}

Keywords: constant; Euler; irrational; Mascheroni; rational; transcendental

Graham's conjecture on tree reconstruction ★★

Author(s): Graham

\begin{problem} for every graph $G$, we let $L(G)$ denote the \Def{line graph} of $G$. Given that $G$ is a tree, can we determine it from the integer sequence $|V(G)|, |V(L(G))|, |V(L(L(G)))|, \ldots$? \end{problem}

Keywords: reconstruction; tree

Vertex Cover Integrality Gap ★★

Author(s): Atserias

\begin{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 \equiv_{\delta n}^{\mathrm{C}} H$ and $\mathrm{vc}(G) \ge (2 - \varepsilon) \cdot \mathrm{vc}(H)$. \end{conjecture}

Keywords: counting quantifiers; FMT12-LesHouches

Big Line or Big Clique in Planar Point Sets ★★

Author(s): Kara; Por; Wood

Let $S$ be a set of points in the plane. Two points $v$ and $w$ in $S$ are \emph{visible} with respect to $S$ if the line segment between $v$ and $w$ contains no other point in $S$.

\begin{conjecture} For all integers $k,\ell\geq2$ there is an integer $n$ such that every set of at least $n$ points in the plane contains at least $\ell$ collinear points or $k$ pairwise visible points. \end{conjecture}

Keywords: Discrete Geometry; Geometric Ramsey Theory

Mixing Circular Colourings

Author(s): Brewster; Noel

\begin{question} Is $\mathfrak{M}_c(G)$ always rational? \end{question}

Keywords: discrete homotopy; graph colourings; mixing

Finite entailment of Positive Horn logic ★★

Author(s): Martin

\begin{question} Positive Horn logic (pH) is the fragment of FO involving exactly $\exists, \forall, \wedge, =$. Does the fragment $pH \wedge \neg pH$ have the finite model property? \end{question}

Keywords: entailment; finite satisfiability; horn logic