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

**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:

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

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: