# Recent Activity

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

Author(s): Aharoni; Berger

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

Keywords: independent set; matroid; partition

## The large sets conjecture ★★★

Author(s): Brown; Graham; Landman

Conjecture   If is 2-large, then is large.

Keywords: 2-large sets; large sets

## Ramsey properties of Cayley graphs ★★★

Author(s): Alon

Conjecture   There exists a fixed constant so that every abelian group has a subset with so that the Cayley graph has no clique or independent set of size .

Keywords: Cayley graph; Ramsey number

## Bases of many weights ★★★

Author(s): Schrijver; Seymour

Let be an (additive) abelian group, and for every let .

Conjecture   Let be a matroid on , let be a map, put and . Then

Keywords: matroid; sumset; zero sum

## The Erdos-Turan conjecture on additive bases ★★★★

Author(s): Erdos; Turan

Let . The representation function for is given by the rule . We call an additive basis if is never .

Conjecture   If is an additive basis, then is unbounded.

## Rota's unimodal conjecture ★★★

Author(s): Rota

Let be a matroid of rank , and for let be the number of closed sets of rank .

Conjecture   is unimodal.
Conjecture   is log-concave.

Keywords: flat; log-concave; matroid

## A conjecture on iterated circumcentres ★★

Author(s): Goddyn

Conjecture   Let be a sequence of points in with the property that for every , the points are distinct, lie on a unique sphere, and further, is the center of this sphere. If this sequence is periodic, must its period be ?

Keywords: periodic; plane geometry; sequence

## Unions of triangle free graphs ★★★

Author(s): Erdos; Hajnal

Problem   Does there exist a graph with no subgraph isomorphic to which cannot be expressed as a union of triangle free graphs?

## The Two Color Conjecture ★★

Author(s): Neumann-Lara

Conjecture   If is an orientation of a simple planar graph, then there is a partition of into so that the graph induced by is acyclic for .

Keywords: acyclic; digraph; planar

## Half-integral flow polynomial values ★★

Author(s): Mohar

Let be the flow polynomial of a graph . So for every positive integer , the value equals the number of nowhere-zero -flows in .

Conjecture   for every 2-edge-connected graph .

Keywords: nowhere-zero flow

## Gao's theorem for nonabelian groups ★★

Author(s): DeVos

For every finite multiplicative group , let () denote the smallest integer so that every sequence of elements of has a subsequence of length (length ) which has product equal to 1 in some order.

Conjecture   for every finite group .

Keywords: subsequence sum; zero sum

## Universal point sets for planar graphs ★★★

Author(s): Mohar

We say that a set is -universal if every vertex planar graph can be drawn in the plane so that each vertex maps to a distinct point in , and all edges are (non-intersecting) straight line segments.

Question   Does there exist an -universal set of size ?

Keywords: geometric graph; planar graph; universal set

## Antichains in the cycle continuous order ★★

Author(s): DeVos

If , are graphs, a function is called cycle-continuous if the pre-image of every element of the (binary) cycle space of is a member of the cycle space of .

Problem   Does there exist an infinite set of graphs so that there is no cycle continuous mapping between and whenever ?

Keywords: antichain; cycle; poset

## Fat 4-polytopes ★★★

Author(s): Eppstein; Kuperberg; Ziegler

The fatness of a 4-polytope is defined to be where is the number of faces of of dimension .

Question   Does there exist a fixed constant so that every convex 4-polytope has fatness at most ?

Keywords: f-vector; polytope

## The Crossing Number of the Complete Bipartite Graph ★★★

Author(s): Turan

The crossing number of is the minimum number of crossings in all drawings of in the plane.

Conjecture

Keywords: complete bipartite graph; crossing number

## Woodall's Conjecture ★★★

Author(s): Woodall

Conjecture   If is a directed graph with smallest directed cut of size , then has disjoint dijoins.

Keywords: digraph; packing

## Pentagon problem ★★★

Author(s): Nesetril

Question   Let be a 3-regular graph that contains no cycle of length shorter than . Is it true that for large enough~ there is a homomorphism ?

Keywords: cubic; homomorphism

## Ryser's conjecture ★★★

Author(s): Ryser

Conjecture   Let be an -uniform -partite hypergraph. If is the maximum number of pairwise disjoint edges in , and is the size of the smallest set of vertices which meets every edge, then .

Keywords: hypergraph; matching; packing

## The Erdös-Hajnal Conjecture ★★★

Author(s): Erdos; Hajnal

Conjecture   For every fixed graph , there exists a constant , so that every graph without an induced subgraph isomorphic to contains either a clique or an independent set of size .

Keywords: induced subgraph