Recent Activity

Ádám's Conjecture ★★★

Author(s): Ádám

Conjecture   Every digraph with at least one directed cycle has an arc whose reversal reduces the number of directed cycles.

Keywords:

Caccetta-Häggkvist Conjecture ★★★★

Author(s): Caccetta; Häggkvist

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

Keywords:

Directed path of length twice the minimum outdegree ★★★

Author(s): Thomassé

Conjecture   Every oriented graph with minimum outdegree $ k $ contains a directed path of length $ 2k $.

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.

Conjecture   Let $ D $ be a digraph. If $ |A(D)| > (k-2) |V(D)| $, then $ D $ contains every antidirected tree of order $ k $.

Keywords:

Decomposing an even tournament in directed paths. ★★★

Author(s): Alspach; Mason; Pullman

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.

Keywords:

Oriented trees in n-chromatic digraphs ★★★

Author(s): Burr

Conjecture   Every digraph with chromatic number at least $ 2k-2 $ contains every oriented tree of order $ k $ as a subdigraph.

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 Discrete Log Problem.

Conjecture   There does not exist a polynomial time algorithm to solve the Discrete Log Problem.

Keywords: discrete log; NP

Good Edge Labelings ★★

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

Question   What is the maximum edge density of a graph which has a good edge labeling?

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

Conjecture   For every $ c<4 $, there is only a finite number of good-edge-labeling critical graphs with average degree less than $ c $.

Keywords: good edge labeling, edge labeling

Transversal achievement game on a square grid ★★

Author(s): Erickson

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?

Keywords: game

Special Primes

Author(s): George BALAN

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

Keywords:

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

Author(s): Payan

Question   Are there any (0,2)-graphs with chromatic number exactly three?

Keywords:

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

Author(s): Noel

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

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

Author(s):

Question   Is Euler-Mascheroni constant an transcendental number?

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

Graham's conjecture on tree reconstruction ★★

Author(s): Graham

Problem   for every graph $ G $, we let $ L(G) $ denote the 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 $?

Keywords: reconstruction; tree

Vertex Cover Integrality Gap ★★

Author(s): Atserias

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

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 visible with respect to $ S $ if the line segment between $ v $ and $ w $ contains no other point in $ S $.

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.

Keywords: Discrete Geometry; Geometric Ramsey Theory

Mixing Circular Colourings

Author(s): Brewster; Noel

Question   Is $ \mathfrak{M}_c(G) $ always rational?

Keywords: discrete homotopy; graph colourings; mixing

Finite entailment of Positive Horn logic ★★

Author(s): Martin

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?

Keywords: entailment; finite satisfiability; horn logic

The Borodin-Kostochka Conjecture ★★

Author(s): Borodin; Kostochka

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

Keywords: