# Recent Activity

## Double-critical graph conjecture ★★

A connected simple graph is called double-critical, if removing any pair of adjacent vertexes lowers the chromatic number by two.

**Conjecture**is the only -chromatic double-critical graph

Keywords: coloring; complete graph

## Shuffle-Exchange Conjecture ★★★

Author(s): Beneš; Folklore; Stone

Given integers , let be the smallest integer such that the symmetric group on the set of all words of length over a -letter alphabet can be generated as ( times), where is the *shuffle permutation* defined by , and is the *exchange group* consisting of all permutations in preserving the first letters in the words.

**Problem (SE)**Evaluate .

**Conjecture (SE)**, for all .

Keywords:

## Strong colorability ★★★

Author(s): Aharoni; Alon; Haxell

Let be a positive integer. We say that a graph is *strongly -colorable* if for every partition of the vertices to sets of size at most there is a proper -coloring of in which the vertices in each set of the partition have distinct colors.

**Conjecture**If is the maximal degree of a graph , then is strongly -colorable.

Keywords: strong coloring

## Is there an algorithm to determine if a triangulated 4-manifold is combinatorially equivalent to the 4-sphere? ★★★

Author(s): Novikov

**Problem**Is there an algorithm which takes as input a triangulated 4-manifold, and determines whether or not this manifold is combinatorially equivalent to the 4-sphere?

## What is the homotopy type of the group of diffeomorphisms of the 4-sphere? ★★★★

Author(s): Smale

**Problem**has the homotopy-type of a product space where is the group of diffeomorphisms of the 4-ball which restrict to the identity on the boundary. Determine some (any?) homotopy or homology groups of .

Keywords: 4-sphere; diffeomorphisms

## Which compact boundaryless 3-manifolds embed smoothly in the 4-sphere? ★★★

Author(s): Kirby

**Problem**Determine a computable set of invariants that allow one to determine, given a compact boundaryless 3-manifold, whether or not it embeds smoothly in the 4-sphere. This should include a constructive procedure to find an embedding if the manifold is embeddable.

Keywords: 3-manifold; 4-sphere; embedding

## Fundamental group torsion for subsets of Euclidean 3-space ★★

Author(s): Ancient/folklore

**Problem**Does there exist a subset of such that its fundamental group has an element of finite order?

Keywords: subsets of euclidean space; torsion

## Which homology 3-spheres bound homology 4-balls? ★★★★

Author(s): Ancient/folklore

**Problem**Is there a complete and computable set of invariants that can determine which (rational) homology -spheres bound (rational) homology -balls?

Keywords: cobordism; homology ball; homology sphere

## Realisation problem for the space of knots in the 3-sphere ★★

Author(s): Budney

**Problem**Given a link in , let the symmetry group of be denoted ie: isotopy classes of diffeomorphisms of which preserve , where the isotopies are also required to preserve .

Now let be a hyperbolic link. Assume has the further `Brunnian' property that there exists a component of such that is the unlink. Let be the subgroup of consisting of diffeomorphisms of which preserve together with its orientation, and which preserve the orientation of .

There is a representation given by restricting the diffeomorphism to the . It's known that is always a cyclic group. And is a signed symmetric group -- the wreath product of a symmetric group with .

Problem: What representations can be obtained?

Keywords: knot space; symmetry

## Slice-ribbon problem ★★★★

Author(s): Fox

**Conjecture**Given a knot in which is slice, is it a ribbon knot?

## Smooth 4-dimensional Schoenflies problem ★★★★

Author(s): Alexander

**Problem**Let be a -dimensional smooth submanifold of , diffeomorphic to . By the Jordan-Brouwer separation theorem, separates into the union of two compact connected -manifolds which share as a common boundary. The Schoenflies problem asks, are these -manifolds diffeomorphic to ? ie: is unknotted?

Keywords: 4-dimensional; Schoenflies; sphere

## Are different notions of the crossing number the same? ★★★

**Problem**Does the following equality hold for every graph ?

The crossing number of a graph is the minimum number of edge crossings in any drawing of in the plane. In the *pairwise crossing number* , we minimize the number of pairs of edges that cross.

Keywords: crossing number; pair-crossing number

## Shuffle-Exchange Conjecture (graph-theoretic form) ★★★

Author(s): Beneš; Folklore; Stone

Given integers , the *2-stage Shuffle-Exchange graph/network*, denoted , is the simple -regular bipartite graph with the ordered pair of linearly labeled parts and , where , such that vertices and are adjacent if and only if (see Fig.1).

Given integers , the *-stage Shuffle-Exchange graph/network*, denoted , is the proper (i.e., respecting all the orders) concatenation of identical copies of (see Fig.1).

Let be the smallest integer such that the graph is rearrangeable.

**Problem**Find .

**Conjecture**.

Keywords:

## Edge-Colouring Geometric Complete Graphs ★★

Author(s): Hurtado

**Question**What is the minimum number of colours such that every complete geometric graph on vertices has an edge colouring such that:

- \item[Variant A] crossing edges get distinct colours, \item[Variant B] disjoint edges get distinct colours, \item[Variant C] non-disjoint edges get distinct colours, \item[Variant D] non-crossing edges get distinct colours.

Keywords: geometric complete graph, colouring

## Number of Cliques in Minor-Closed Classes ★★

Author(s): Wood

**Question**Is there a constant such that every -vertex -minor-free graph has at most cliques?

## A gold-grabbing game ★★

Author(s): Rosenfeld

** Setup** Fix a tree and for every vertex a non-negative integer which we think of as the amount of *gold* at .

**2-Player game** Players alternate turns. On each turn, a player chooses a leaf vertex of the tree, takes the gold at this vertex, and then deletes . The game ends when the tree is empty, and the winner is the player who has accumulated the most gold.

**Problem**Find optimal strategies for the players.

## Circular colouring the orthogonality graph ★★

Author(s): DeVos; Ghebleh; Goddyn; Mohar; Naserasr

Let denote the graph with vertex set consisting of all lines through the origin in and two vertices adjacent in if they are perpendicular.

**Problem**Is ?

Keywords: circular coloring; geometric graph; orthogonality

## Crossing numbers and coloring ★★★

Author(s): Albertson

We let denote the crossing number of a graph .

**Conjecture**Every graph with satisfies .

Keywords: coloring; complete graph; crossing number

## Domination in cubic graphs ★★

Author(s): Reed

**Problem**Does every 3-connected cubic graph satisfy ?

Keywords: cubic graph; domination

## A generalization of Vizing's Theorem? ★★

Author(s): Rosenfeld

**Conjecture**Let be a simple -uniform hypergraph, and assume that every set of points is contained in at most edges. Then there exists an -edge-coloring so that any two edges which share vertices have distinct colors.

Keywords: edge-coloring; hypergraph; Vizing