# Recent Activity

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

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

## Ádám's Conjecture ★★★

Author(s): Ádám

**Conjecture**Every digraph with at least one directed cycle has an arc whose reversal reduces the number of directed cycles.

Keywords:

## Caccetta-Häggkvist Conjecture ★★★★

Author(s): Caccetta; Häggkvist

**Conjecture**Every simple digraph of order with minimum outdegree at least has a cycle with length at most

Keywords:

## Directed path of length twice the minimum outdegree ★★★

Author(s): Thomassé

**Conjecture**Every oriented graph with minimum outdegree contains a directed path of length .

Keywords:

## Antidirected trees in digraphs ★★

Author(s): Addario-Berry; Havet; Linhares Sales; Reed; Thomassé

An antidirected tree is an orientation of a tree in which every vertex has either indegree 0 or outdergree 0.

**Conjecture**Let be a digraph. If , then contains every antidirected tree of order .

Keywords:

## Decomposing an even tournament in directed paths. ★★★

Author(s): Alspach; Mason; Pullman

**Conjecture**Every tournament on an even number of vertices can be decomposed into directed paths.

Keywords:

## Oriented trees in n-chromatic digraphs ★★★

Author(s): Burr

**Conjecture**Every digraph with chromatic number at least contains every oriented tree of order as a subdigraph.

Keywords: