# Recent Activity

## The intersection of two perfect matchings ★★

**Conjecture**Every bridgeless cubic graph has two perfect matchings , so that does not contain an odd edge-cut.

Keywords: cubic; nowhere-zero flow; perfect matching

## Counterexamples to the Baillie-PSW primality test ★★

Author(s):

**Problem (1)**Find a counterexample to Baillie-PSW primality test or prove that there is no one.

**Problem (2)**Find a composite or which divides both (see Fermat pseudoprime) and the Fibonacci number (see Lucas pseudoprime), or prove that there is no such .

Keywords:

## A sextic counterexample to Euler's sum of powers conjecture ★★

Author(s): Euler

**Problem**Find six positive integers such that or prove that such integers do not exist.

Keywords:

## Geodesic cycles and Tutte's Theorem ★★

Author(s): Georgakopoulos; Sprüssel

**Problem**If is a -connected finite graph, is there an assignment of lengths to the edges of , such that every -geodesic cycle is peripheral?

Keywords: cycle space; geodesic cycles; peripheral cycles

## Oriented chromatic number of planar graphs ★★

Author(s):

An oriented colouring of an oriented graph is assignment of colours to the vertices such that no two arcs receive ordered pairs of colours and . It is equivalent to a homomorphism of the digraph onto some tournament of order .

**Problem**What is the maximal possible oriented chromatic number of an oriented planar graph?

Keywords: oriented coloring; oriented graph; planar graph

## Covering systems with big moduli ★★

**Problem**Does for every integer exist a covering system with all moduli distinct and at least equal to~?

Keywords: covering system

## Odd incongruent covering systems ★★★

**Conjecture**There is no covering system whose moduli are odd, distinct, and greater than 1.

Keywords: covering system

## Hamiltonian cycles in powers of infinite graphs ★★

Author(s): Georgakopoulos

**Conjecture**

- \item If is a countable connected graph then its third power is hamiltonian. \item If is a 2-connected countable graph then its square is hamiltonian.

Keywords: hamiltonian; infinite graph

## Hamiltonian cycles in line graphs of infinite graphs ★★

Author(s): Georgakopoulos

**Conjecture**

- \item If is a 4-edge-connected locally finite graph, then its line graph is hamiltonian. \item If the line graph of a locally finite graph is 4-connected, then is hamiltonian.

Keywords: hamiltonian; infinite graph; line graphs

## Infinite uniquely hamiltonian graphs ★★

Author(s): Mohar

**Problem**Are there any uniquely hamiltonian locally finite 1-ended graphs which are regular of degree ?

Keywords: hamiltonian; infinite graph; uniquely hamiltonian

## Linear-size circuits for stable $0,1 < 2$ sorting? ★★

Author(s): Regan

**Problem**Can -size circuits compute the function on defined inductively by , , , and ?

## Unconditional derandomization of Arthur-Merlin games ★★★

Keywords: Arthur-Merlin; Hitting Sets; unconditional

## Subset-sums equality (pigeonhole version) ★★★

Author(s):

**Problem**Let be natural numbers with . It follows from the pigeon-hole principle that there exist distinct subsets with . Is it possible to find such a pair in polynomial time?

Keywords: polynomial algorithm; search problem

## Weak pentagon problem ★★

Author(s): Samal

**Conjecture**If is a cubic graph not containing a triangle, then it is possible to color the edges of by five colors, so that the complement of every color class is a bipartite graph.

Keywords: Clebsch graph; cut-continuous mapping; edge-coloring; homomorphism; pentagon

## Lonely runner conjecture ★★★

**Conjecture**Suppose runners having distinct constant speeds start at a common point and run laps on a circular track with circumference 1. Then for any given runner, there is a time at which that runner is distance at least (along the track) away from every other runner.

Keywords: diophantine approximation; view obstruction

## Mapping planar graphs to odd cycles ★★★

Author(s): Jaeger

**Conjecture**Every planar graph of girth has a homomorphism to .

Keywords: girth; homomorphism; planar graph

## 5-local-tensions ★★

Author(s): DeVos

**Conjecture**There exists a fixed constant (probably suffices) so that every embedded (loopless) graph with edge-width has a 5-local-tension.

## Concavity of van der Waerden numbers ★★

Author(s): Landman

For and positive integers, the (mixed) van der Waerden number is the least positive integer such that every (red-blue)-coloring of admits either a -term red arithmetic progression or an -term blue arithmetic progression.

**Conjecture**For all and with , .

Keywords: arithmetic progression; van der Waerden

## Circular coloring triangle-free subcubic planar graphs ★★

**Problem**Does every triangle-free planar graph of maximum degree three have circular chromatic number at most ?

Keywords: circular coloring; planar graph; triangle free