# Recent Activity

## List Total Colouring Conjecture ★★

Author(s): Borodin; Kostochka; Woodall

**Conjecture**If is the total graph of a multigraph, then .

Keywords: list coloring; Total coloring; total graphs

## Partitioning the Projective Plane ★★

Author(s): Noel

Throughout this post, by *projective plane* we mean the set of all lines through the origin in .

**Definition**Say that a subset of the projective plane is

*octahedral*if all lines in pass through the closure of two opposite faces of a regular octahedron centered at the origin.

**Definition**Say that a subset of the projective plane is

*weakly octahedral*if every set such that is octahedral.

**Conjecture**Suppose that the projective plane can be partitioned into four sets, say and such that each set is weakly octahedral. Then each is octahedral.

Keywords: Partitioning; projective plane

## Kriesell's Conjecture ★★

Author(s): Kriesell

**Conjecture**Let be a graph and let such that for any pair there are edge-disjoint paths from to in . Then contains edge-disjoint trees, each of which contains .

Keywords: Disjoint paths; edge-connectivity; spanning trees

## 2-colouring a graph without a monochromatic maximum clique ★★

**Conjecture**If is a non-empty graph containing no induced odd cycle of length at least , then there is a -vertex colouring of in which no maximum clique is monochromatic.

Keywords: maximum clique; Partitioning

## Almost all non-Hamiltonian 3-regular graphs are 1-connected ★★

Author(s): Haythorpe

**Conjecture**Denote by the number of non-Hamiltonian 3-regular graphs of size , and similarly denote by the number of non-Hamiltonian 3-regular 1-connected graphs of size .

Is it true that ?

## Erdős–Faber–Lovász conjecture ★★★

Author(s): Erdos; Faber; Lovasz

**Conjecture**If is a simple graph which is the union of pairwise edge-disjoint complete graphs, each of which has vertices, then the chromatic number of is .

Keywords: chromatic number

## Are there only finite Fermat Primes? ★★★

Author(s):

**Conjecture**A Fermat prime is a Fermat number that is prime. The only known Fermat primes are F_0 =3,F_1=5,F_2=17,F_3 =257 ,F_4=65537 It is unknown if other fermat primes exist.

Keywords:

## Are all Fermat Numbers square-free? ★★★

Author(s):

**Conjecture**Are all Fermat Numbers Square-Free?

Keywords:

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

## Choosability of Graph Powers ★★

Author(s): Noel

**Question (Noel, 2013)**Does there exist a function such that for every graph ,

Keywords: choosability; chromatic number; list coloring; square of a graph

## Erdős-Posa property for long directed cycles ★★

**Conjecture**Let be an integer. For every integer , there exists an integer such that for every digraph , either has a pairwise-disjoint directed cycles of length at least , or there exists a set of at most vertices such that has no directed cycles of length at least .

Keywords:

## Large acyclic induced subdigraph in a planar oriented graph. ★★

Author(s): Harutyunyan

**Conjecture**Every planar oriented graph has an acyclic induced subdigraph of order at least .

Keywords:

## Polignac's Conjecture ★★★

Author(s): de Polignac

**Conjecture**Polignac's Conjecture: For any positive even number n, there are infinitely many prime gaps of size n. In other words: There are infinitely many cases of two consecutive prime numbers with difference n.

In particular, this implies:

**Conjecture**Twin Prime Conjecture: There are an infinite number of twin primes.

## Alexa's Conjecture on Primality ★★

Author(s): Alexa

**Definition**Let be the unique integer (with respect to a fixed ) such that

**Conjecture**A natural number is a prime iff

Keywords: primality

## P vs. BPP ★★★

Author(s): Folklore

**Conjecture**Can all problems that can be computed by a probabilistic Turing machine (with error probability < 1/3) in polynomial time be solved by a deterministic Turing machine in polynomial time? That is, does P = BPP?

Keywords: BPP; circuit complexity; pseudorandom generators

## Goldbach conjecture ★★★★

Author(s): Goldbach

**Conjecture**Every even integer greater than 2 is the sum of two primes.

Keywords: additive basis; prime

## Goldberg's conjecture ★★★

Author(s): Goldberg

The *overfull parameter* is defined as follows:

**Conjecture**Every graph satisfies .

Keywords: edge-coloring; multigraph

## Cyclic spanning subdigraph with small cyclomatic number ★★

Author(s): Bondy

**Conjecture**Let be a digraph all of whose strong components are nontrivial. Then contains a cyclic spanning subdigraph with cyclomatic number at most .

Keywords:

## inverse of an integer matrix ★★

Author(s): Gregory

**Question**I've been working on this for a long time and I'm getting nowhere. Could you help me or at least tell me where to look for help. Suppose D is an m-by-m diagonal matrix with integer elements all . Suppose X is an m-by-n integer matrix . Consider the partitioned matrix M = [D X]. Obviously M has full row rank so it has a right inverse of rational numbers. The question is, under what conditions does it have an integer right inverse? My guess, which I can't prove, is that the integers in each row need to be relatively prime.

Keywords: invertable matrices, integer matrices

## Minimum number of arc-disjoint transitive subtournaments of order 3 in a tournament ★★

Author(s): Yuster

**Conjecture**If is a tournament of order , then it contains arc-disjoint transitive subtournaments of order 3.

Keywords: