# Recent Activity

## 3-Edge-Coloring Conjecture ★★★

Author(s): Arthur; Hoffmann-Ostenhof

Conjecture   Suppose with is a connected cubic graph admitting a -edge coloring. Then there is an edge such that the cubic graph homeomorphic to has a -edge coloring.

Keywords: 3-edge coloring; 4-flow; removable edge

## r-regular graphs are not uniquely hamiltonian. ★★★

Author(s): Sheehan

Conjecture   If is a finite -regular graph, where , then is not uniquely hamiltonian.

Keywords: hamiltonian; regular; uniquely hamiltonian

## Partition of Complete Geometric Graph into Plane Trees ★★

Author(s):

Conjecture   Every complete geometric graph with an even number of vertices has a partition of its edge set into plane (i.e. non-crossing) spanning trees.

## Smooth 4-dimensional Poincare conjecture ★★★★

Author(s): Poincare; Smale; Stallings

Conjecture   If a -manifold has the homotopy type of the -sphere , is it diffeomorphic to ?

Keywords: 4-manifold; poincare; sphere

## Book Thickness of Subdivisions ★★

Author(s): Blankenship; Oporowski

Let be a finite undirected simple graph.

A -page book embedding of consists of a linear order of and a (non-proper) -colouring of such that edges with the same colour do not cross with respect to . That is, if for some edges , then and receive distinct colours.

One can think that the vertices are placed along the spine of a book, and the edges are drawn without crossings on the pages of the book.

The book thickness of , denoted by bt is the minimum integer for which there is a -page book embedding of .

Let be the graph obtained by subdividing each edge of exactly once.

Conjecture   There is a function such that for every graph , Keywords: book embedding; book thickness

## Primitive pythagorean n-tuple tree ★★

Author(s):

Conjecture   Find linear transformation construction of primitive pythagorean n-tuple tree!

Keywords:

## Jacobian Conjecture ★★★

Author(s): Keller

Conjecture   Let be a field of characteristic zero. A collection of polynomials in variables defines an automorphism of if and only if the Jacobian matrix is a nonzero constant.

Keywords: Affine Geometry; Automorphisms; Polynomials

## Inscribed Square Problem ★★

Author(s): Toeplitz

Conjecture   Does every Jordan curve have 4 points on it which form the vertices of a square?

Keywords: simple closed curve; square

## Complete bipartite subgraphs of perfect graphs ★★

Author(s): Fox

Problem   Let be a perfect graph on vertices. Is it true that either or contains a complete bipartite subgraph with bipartition so that ?

Keywords: perfect graph

## Transversal achievement game on a square grid ★★

Author(s): Erickson

Problem   Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an grid. The first player (if any) to occupy a set of cells having no two cells in the same row or column is the winner. What is the outcome of the game given optimal play?

Keywords: game

## Graceful Tree Conjecture ★★★

Author(s):

Conjecture   All trees are graceful

Keywords: combinatorics; graceful labeling

## Extremal problem on the number of tree endomorphism ★★

Author(s): Zhicong Lin

Conjecture   An endomorphism of a graph is a mapping on the vertex set of the graph which preserves edges. Among all the vertices' trees, the star with vertices has the most endomorphisms, while the path with vertices has the least endomorphisms.

Keywords:

## 3-Colourability of Arrangements of Great Circles ★★

Consider a set of great circles on a sphere with no three circles meeting at a point. The arrangement graph of has a vertex for each intersection point, and an edge for each arc directly connecting two intersection points. So this arrangement graph is 4-regular and planar.

Conjecture   Every arrangement graph of a set of great circles is -colourable.

Keywords: arrangement graph; graph coloring

## KPZ Universality Conjecture ★★★

Author(s):

Conjecture   Formulate a central limit theorem for the KPZ universality class.

Keywords: KPZ equation, central limit theorem

## Friendly partitions ★★

Author(s): DeVos

A friendly partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbours in its own class as in the other.

Problem   Is it true that for every , all but finitely many -regular graphs have friendly partitions?

Keywords: edge-cut; partition; regular

## Finite entailment of Positive Horn logic ★★

Author(s): Martin

Question   Positive Horn logic (pH) is the fragment of FO involving exactly . Does the fragment have the finite model property?

Keywords: entailment; finite satisfiability; horn logic

## Triangle free strongly regular graphs ★★★

Author(s):

Problem   Is there an eighth triangle free strongly regular graph?

Keywords: strongly regular; triangle free

## A discrete iteration related to Pierce expansions ★★

Author(s): Shallit

Conjecture   Let be integers. Set and for . Eventually we have ; put .

Example: , since , , , , , , , .

Prove or disprove: .

Keywords: Pierce expansions

## Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★

Author(s): Kostochka; Reed

Conjecture   A triangle-free graph with maximum degree has chromatic number at most .

Keywords: chromatic number; girth; maximum degree; triangle free

## Hedetniemi's Conjecture ★★★

Author(s): Hedetniemi

Conjecture   If are simple finite graphs, then .

Here is the tensor product (also called the direct or categorical product) of and .