Recent Activity

Arc-disjoint strongly connected spanning subdigraphs ★★

Author(s): Bang-Jensen; Yeo

Conjecture   There exists an ineteger $ k $ so that every $ k $-arc-connected digraph contains a pair of arc-disjoint strongly connected spanning subdigraphs?

Keywords:

Arc-disjoint out-branching and in-branching ★★

Author(s): Thomassen

Conjecture   There exists an integer $ k $ such that every $ k $-arc-strong digraph $ D $ with specified vertices $ u $ and $ v $ contains an out-branching rooted at $ u $ and an in-branching rooted at $ v $ which are arc-disjoint.

Keywords:

Strong edge colouring conjecture ★★

Author(s): Erdos; Nesetril

A strong edge-colouring of a graph $ G $ is a edge-colouring in which every colour class is an induced matching; that is, any two vertices belonging to distinct edges with the same colour are not adjacent. The strong chromatic index $ s\chi'(G) $ is the minimum number of colours in a strong edge-colouring of $ G $.

Conjecture   $$s\chi'(G) \leq \frac{5\Delta^2}{4}, \text{if $\Delta$ is even,}$$ $$s\chi'(G) \leq \frac{5\Delta^2-2\Delta +1}{4},&\text{if $\Delta$ is odd.}$$

Keywords:

Long directed cycles in diregular digraphs ★★★

Author(s): Jackson

Conjecture   Every strong oriented graph in which each vertex has indegree and outdegree at least $ d $ contains a directed cycle of length at least $ 2d+1 $.

Keywords:

Splitting a digraph with minimum outdegree constraints ★★★

Author(s): Alon

Problem   Is there a minimum integer $ f(d) $ such that the vertices of any digraph with minimum outdegree $ d $ can be partitioned into two classes so that the minimum outdegree of the subgraph induced by each class is at least $ d $?

Keywords:

Stable set meeting all longest directed paths. ★★

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

Conjecture   Every digraph has a stable set meeting all longest directed paths

Keywords:

Á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