# Recent Activity

## The intersection of two perfect matchings ★★

Author(s): Macajova; Skoviera

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

Author(s): Erdos; Selfridge

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

Author(s): Erdos; Selfridge

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

## Hamiltonian cycles in line graphs ★★★

Author(s): Thomassen

Conjecture   Every 4-connected line graph is hamiltonian.

Keywords: hamiltonian; 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 ?

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

Author(s): Regan

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

Keywords: Circuits; sorting

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

Author(s): Shaltiel; Umans

Problem   Prove unconditionally that .

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.

## Lonely runner conjecture ★★★

Author(s): Cusick; Wills

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.

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

Keywords: coloring; surface; 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 ★★

Author(s): Ghebleh; Zhu

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

Keywords: circular coloring; planar graph; triangle free