# Recent Activity

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

Author(s): Kühn; Osthus

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

Author(s): Kühn; Osthus

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

Author(s): Abertson; Berman

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:

## Coloring the union of degenerate graphs ★★

Author(s): Tarsi

Conjecture   The union of a -degenerate graph (a forest) and a -degenerate graph is -colourable.

Keywords:

## Arc-disjoint strongly connected spanning subdigraphs ★★

Author(s): Bang-Jensen; Yeo

Conjecture   There exists an ineteger so that every -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 such that every -arc-strong digraph with specified vertices and contains an out-branching rooted at and an in-branching rooted at which are arc-disjoint.

Keywords:

## Strong edge colouring conjecture ★★

Author(s): Erdos; Nesetril

A strong edge-colouring of a graph 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 is the minimum number of colours in a strong edge-colouring of .

Conjecture  Keywords: