# Recent Activity

## Decomposing k-arc-strong tournament into k spanning strong digraphs ★★

Author(s): Bang-Jensen; Yeo

**Conjecture**Every k-arc-strong tournament decomposes into k spanning strong digraphs.

Keywords:

## PTAS for feedback arc set in tournaments ★★

**Question**Is there a polynomial time approximation scheme for the feedback arc set problem for the class of tournaments?

Keywords: feedback arc set; PTAS; tournament

## Partitionning a tournament into k-strongly connected subtournaments. ★★

Author(s): Thomassen

**Problem**Let be positve integer Does there exists an integer such that every -strong tournament admits a partition of its vertex set such that the subtournament induced by is a non-trivial -strong for all .

Keywords:

## Weighted colouring of hexagonal graphs. ★★

**Conjecture**There is an absolute constant such that for every hexagonal graph and vertex weighting ,

Keywords:

## Colouring the square of a planar graph ★★

Author(s): Wegner

**Conjecture**Let be a planar graph of maximum degree . The chromatic number of its square is

- \item at most if , \item at most if , \item at most if .

Keywords:

## List chromatic number and maximum degree of bipartite graphs ★★

Author(s): Alon

**Conjecture**There is a constant such that the list chromatic number of any bipartite graph of maximum degree is at most .

Keywords:

## Hamilton decomposition of prisms over 3-connected cubic planar graphs ★★

**Conjecture**Every prism over a -connected cubic planar graph can be decomposed into two Hamilton cycles.

Keywords:

## Turán's problem for hypergraphs ★★

Author(s): Turan

**Conjecture**Every simple -uniform hypergraph on vertices which contains no complete -uniform hypergraph on four vertices has at most hyperedges.

**Conjecture**Every simple -uniform hypergraph on vertices which contains no complete -uniform hypergraph on five vertices has at most hyperedges.

Keywords:

## 4-connected graphs are not uniquely hamiltonian ★★

Author(s): Fleischner

**Conjecture**Every -connected graph with a Hamilton cycle has a second Hamilton cycle.

Keywords:

## Every prism over a 3-connected planar graph is hamiltonian. ★★

Author(s): Kaiser; Král; Rosenfeld; Ryjácek; Voss

**Conjecture**If is a -connected planar graph, then has a Hamilton cycle.

Keywords:

## Hoàng-Reed Conjecture ★★★

**Conjecture**Every digraph in which each vertex has outdegree at least contains directed cycles such that meets in at most one vertex, .

Keywords:

## Edge-disjoint Hamilton cycles in highly strongly connected tournaments. ★★

Author(s): Thomassen

**Conjecture**For every , there is an integer so that every strongly -connected tournament has edge-disjoint Hamilton cycles.

Keywords:

## Hamilton cycle in small d-diregular graphs ★★

Author(s): Jackson

An directed graph is -diregular if every vertex has indegree and outdegree at least .

**Conjecture**For , every -diregular oriented graph on at most vertices has a Hamilton cycle.

Keywords:

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