# Recent Activity

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

## Long directed cycles in diregular digraphs ★★★

Author(s): Jackson

**Conjecture**Every strong oriented graph in which each vertex has indegree and outdegree at least contains a directed cycle of length at least .

Keywords:

## Splitting a digraph with minimum outdegree constraints ★★★

Author(s): Alon

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

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: