# Recent Activity

## Are almost all graphs determined by their spectrum? ★★★

Author(s):

**Problem**Are almost all graphs uniquely determined by the spectrum of their adjacency matrix?

Keywords: cospectral; graph invariant; spectrum

## Signing a graph to have small magnitude eigenvalues ★★

**Conjecture**If is the adjacency matrix of a -regular graph, then there is a symmetric signing of (i.e. replace some entries by ) so that the resulting matrix has all eigenvalues of magnitude at most .

Keywords: eigenvalue; expander; Ramanujan graph; signed graph; signing

## The Bollobás-Eldridge-Catlin Conjecture on graph packing ★★★

Author(s):

**Conjecture (BEC-conjecture)**If and are -vertex graphs and , then and pack.

Keywords: graph packing

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