# Recent Activity

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

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

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

## List colorings of edge-critical graphs ★★

Author(s): Mohar

**Conjecture**Suppose that is a -edge-critical graph. Suppose that for each edge of , there is a list of colors. Then is -edge-colorable unless all lists are equal to each other.

Keywords: edge-coloring; list coloring

## Aharoni-Berger conjecture ★★★

**Conjecture**If are matroids on and for every partition of , then there exists with which is independent in every .

Keywords: independent set; matroid; partition