# Recent Activity

## Switching reconstruction of digraphs ★★

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

Keywords:

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

Keywords:

## Acyclic list colouring of planar graphs. ★★★

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

**Conjecture**Every planar graph is acyclically 5-choosable.

Keywords:

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

Keywords:

## Triangle-packing vs triangle edge-transversal. ★★

Author(s): Tuza

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

Keywords:

## Odd-cycle transversal in triangle-free graphs ★★

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

**Conjecture**If is a simple triangle-free graph, then there is a set of at most edges whose deletion destroys every odd cycle.

Keywords:

## Simultaneous partition of hypergraphs ★★

**Problem**Let and be two -uniform hypergraph on the same vertex set . Does there always exist a partition of into classes such that for both , at least hyperedges of meet each of the classes ?

Keywords:

## Complexity of the H-factor problem. ★★

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

**Problem**Let be a fixed positive real number and a fixed graph. Is it NP-hard to determine whether a graph on vertices and minimum degree contains and -factor?

Keywords:

## Subgraph of large average degree and large girth. ★★

Author(s): Thomassen

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

Keywords:

## Turán number of a finite family. ★★

Author(s): Erdos; Simonovits

Given a finite family of graphs and an integer , the Turán number of is the largest integer such that there exists a graph on vertices with edges which contains no member of as a subgraph.

**Conjecture**For every finite family of graphs there exists an such that .

Keywords:

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

Author(s): Mader

**Conjecture**For all there is an integer such that every digraph of minimum outdegree at least contains a subdivision of a transitive tournament of order .

Keywords:

## Large induced forest in a planar graph. ★★

**Conjecture**Every planar graph on verices has an induced forest with at least vertices.

Keywords:

## Lovász Path Removal Conjecture ★★

Author(s): Lovasz

**Conjecture**There is an integer-valued function such that if is any -connected graph and and are any two vertices of , then there exists an induced path with ends and such that is -connected.

Keywords:

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

Author(s): Kelmans

**Problem**Does every -connected cubic graph on vertices admit a partition into paths of length ?

Keywords:

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

Author(s): Sabidussi

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

Keywords:

## Decomposing an eulerian graph into cycles. ★★

Author(s): Hajós

**Conjecture**Every simple eulerian graph on vertices can be decomposed into at most cycles.

Keywords:

## Decomposing a connected graph into paths. ★★★

Author(s): Gallai

**Conjecture**Every simple connected graph on vertices can be decomposed into at most paths.

Keywords:

## Melnikov's valency-variety problem ★

Author(s): Melnikov

**Problem**The valency-variety of a graph is the number of different degrees in . Is the chromatic number of any graph with at least two vertices greater than

Keywords:

## Do any three longest paths in a connected graph have a vertex in common? ★★

Author(s): Gallai

**Conjecture**Do any three longest paths in a connected graph have a vertex in common?

Keywords: