Recent Activity

Switching reconstruction of digraphs ★★

Author(s): Bondy; Mercier

Question   Are there any switching-nonreconstructible digraphs on twelve or more vertices?


Switching reconstruction conjecture ★★

Author(s): Stanley

Conjecture   Every simple graph on five or more vertices is switching-reconstructible.

Keywords: reconstruction

Every 4-connected toroidal graph has a Hamilton cycle ★★

Author(s): Grunbaum; Nash-Williams

Conjecture   Every 4-connected toroidal graph has a Hamilton cycle.


Acyclic list colouring of planar graphs. ★★★

Author(s): Borodin; Fon-Der-Flasss; Kostochka; Raspaud; Sopena

Conjecture   Every planar graph is acyclically 5-choosable.


Earth-Moon Problem ★★

Author(s): Ringel

Problem   What is the maximum number of colours needed to colour countries such that no two countries sharing a common border have the same colour in the case where each country consists of one region on earth and one region on the moon ?


Triangle-packing vs triangle edge-transversal. ★★

Author(s): Tuza

Conjecture   If $ G $ has at most $ k $ edge-disjoint triangles, then there is a set of $ 2k $ edges whose deletion destroys every triangle.


Odd-cycle transversal in triangle-free graphs ★★

Author(s): Erdos; Faudree; Pach; Spencer

Conjecture   If $ G $ is a simple triangle-free graph, then there is a set of at most $ n^2/25 $ edges whose deletion destroys every odd cycle.


Simultaneous partition of hypergraphs ★★

Author(s): Kühn; Osthus

Problem   Let $ H_1 $ and $ H_2 $ be two $ r $-uniform hypergraph on the same vertex set $ V $. Does there always exist a partition of $ V $ into $ r $ classes $ V_1, \dots , V_r $ such that for both $ i=1,2 $, at least $ r!m_i/r^r -o(m_i) $ hyperedges of $ H_i $ meet each of the classes $ V_1, \dots , V_r $?


Complexity of the H-factor problem. ★★

Author(s): Kühn; Osthus

An $ H $-factor in a graph $ G $ is a set of vertex-disjoint copies of $ H $ covering all vertices of $ G $.

Problem  Let $ c $ be a fixed positive real number and $ H $ a fixed graph. Is it NP-hard to determine whether a graph $ G $ on $ n $ vertices and minimum degree $ cn $ contains and $ H $-factor?


Subgraph of large average degree and large girth. ★★

Author(s): Thomassen

Conjecture   For all positive integers $ g $ and $ k $, there exists an integer $ d $ such that every graph of average degree at least $ d $ contains a subgraph of average degree at least $ k $ and girth greater than $ g $.


Turán number of a finite family. ★★

Author(s): Erdos; Simonovits

Given a finite family $ {\cal F} $ of graphs and an integer $ n $, the Turán number $ ex(n,{\cal F}) $ of $ {\cal F} $ is the largest integer $ m $ such that there exists a graph on $ n $ vertices with $ m $ edges which contains no member of $ {\cal F} $ as a subgraph.

Conjecture   For every finite family $ {\cal F} $ of graphs there exists an $ F\in {\cal F} $ such that $ ex(n, F ) = O(ex(n, {\cal F})) $ .


Subdivision of a transitive tournament in digraphs with large outdegree. ★★

Author(s): Mader

Conjecture   For all $ k $ there is an integer $ f(k) $ such that every digraph of minimum outdegree at least $ f(k) $ contains a subdivision of a transitive tournament of order $ k $.


Large induced forest in a planar graph. ★★

Author(s): Abertson; Berman

Conjecture   Every planar graph on $ n $ verices has an induced forest with at least $ n/2 $ vertices.


Lovász Path Removal Conjecture ★★

Author(s): Lovasz

Conjecture   There is an integer-valued function $ f(k) $ such that if $ G $ is any $ f(k) $-connected graph and $ x $ and $ y $ are any two vertices of $ G $, then there exists an induced path $ P $ with ends $ x $ and $ y $ such that $ G-V(P) $ is $ k $-connected.


Partition of a cubic 3-connected graphs into paths of length 2. ★★

Author(s): Kelmans

Problem   Does every $ 3 $-connected cubic graph on $ 3k $ vertices admit a partition into $ k $ paths of length $ 2 $?


Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour. ★★

Author(s): Sabidussi

Conjecture   Let $ G $ be an eulerian graph of minimum degree $ 4 $, and let $ W $ be an eulerian tour of $ G $. Then $ G $ admits a decomposition into cycles none of which contains two consecutive edges of $ W $.


Decomposing an eulerian graph into cycles. ★★

Author(s): Hajós

Conjecture   Every simple eulerian graph on $ n $ vertices can be decomposed into at most $ \frac{1}{2}(n-1) $ cycles.


Decomposing a connected graph into paths. ★★★

Author(s): Gallai

Conjecture   Every simple connected graph on $ n $ vertices can be decomposed into at most $ \frac{1}{2}(n+1) $ paths.


Melnikov's valency-variety problem

Author(s): Melnikov

Problem   The valency-variety $ w(G) $ of a graph $ G $ is the number of different degrees in $ G $. Is the chromatic number of any graph $ G $ with at least two vertices greater than $$\ceil{ \frac{\floor{w(G)/2}}{|V(G)| - w(G)} } ~ ?$$


Coloring the union of degenerate graphs ★★

Author(s): Tarsi

Conjecture   The union of a $ 1 $-degenerate graph (a forest) and a $ 2 $-degenerate graph is $ 5 $-colourable.