# Recent Activity

## Á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}

Keywords:

## 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}

Keywords:

## 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}

Keywords:

## 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}

Keywords:

## 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}

Keywords:

## 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}

Keywords:

## Discrete Logarithm Problem ★★★

Author(s):

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}

Keywords:

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

Author(s): Payan

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

Keywords:

## 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}

## 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 ★★★

Author(s):

\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}

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

## The Borodin-Kostochka Conjecture ★★

Author(s): Borodin; Kostochka

\begin{conjecture} Every graph with maximum degree $\Delta \geq 9$ has chromatic number at most $\max\{\Delta-1, \omega\}$. \end{conjecture}

Keywords: