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

Keywords: complete geometric graph, edge colouring

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

Author(s): Felsner; Hurtado; Noy; Streinu

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?

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

**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 .

Keywords: categorical product; coloring; homomorphism; tensor product