# Recent Activity

## Odd cycles and low oddness ★★

Author(s):

Conjecture   If in a bridgeless cubic graph the cycles of any -factor are odd, then , where denotes the oddness of the graph , that is, the minimum number of odd cycles in a -factor of .

Keywords:

## Odd perfect numbers ★★★

Author(s): Ancient/folklore

Conjecture   There is no odd perfect number.

Keywords: perfect number

## Matching cut and girth ★★

Author(s):

Question   For every does there exists a such that every graph with average degree smaller than and girth at least has a matching-cut?

Keywords: matching cut, matching, cut

## Strong 5-cycle double cover conjecture ★★★

Author(s): Arthur; Hoffmann-Ostenhof

Conjecture   Let be a circuit in a bridgeless cubic graph . Then there is a five cycle double cover of such that is a subgraph of one of these five cycles.

Keywords: cycle cover

## Petersen coloring conjecture ★★★

Author(s): Jaeger

Conjecture   Let be a cubic graph with no bridge. Then there is a coloring of the edges of using the edges of the Petersen graph so that any three mutually adjacent edges of map to three mutually adjancent edges in the Petersen graph.

Keywords: cubic; edge-coloring; Petersen graph

## Characterizing (aleph_0,aleph_1)-graphs ★★★

Call a graph an -graph if it has a bipartition so that every vertex in has degree and every vertex in has degree .

Problem   Characterize the -graphs.

## The Berge-Fulkerson conjecture ★★★★

Author(s): Berge; Fulkerson

Conjecture   If is a bridgeless cubic graph, then there exist 6 perfect matchings of with the property that every edge of is contained in exactly two of .

Keywords: cubic; perfect matching

## Obstacle number of planar graphs ★

Author(s): Alpert; Koch; Laison

Does there exist a planar graph with obstacle number greater than 1? Is there some such that every planar graph has obstacle number at most ?

## Twin prime conjecture ★★★★

Author(s):

Conjecture   There exist infinitely many positive integers so that both and are prime.

Keywords: prime; twin prime

## Cores of strongly regular graphs ★★★

Author(s): Cameron; Kazanidis

Question   Does every strongly regular graph have either itself or a complete graph as a core?

Keywords: core; strongly regular

## Square achievement game on an n x n grid ★★

Author(s): Erickson

Problem   Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an grid. The first player (if any) to occupy four cells at the vertices of a square with horizontal and vertical sides is the winner. What is the outcome of the game given optimal play? Note: Roland Bacher and Shalom Eliahou proved that every 15 x 15 binary matrix contains four equal entries (all 0's or all 1's) at the vertices of a square with horizontal and vertical sides. So the game must result in a winner (the first player) when n=15.

Keywords: game

## What is the largest graph of positive curvature? ★

Author(s): DeVos; Mohar

Problem   What is the largest connected planar graph of minimum degree 3 which has everywhere positive combinatorial curvature, but is not a prism or antiprism?

Keywords: curvature; planar graph

## Extension complexity of (convex) polygons ★★

Author(s):

The extension complexity of a polytope is the minimum number for which there exists a polytope with facets and an affine mapping with .

Question   Does there exists, for infinitely many integers , a convex polygon on vertices whose extension complexity is ?

## Strict inequalities for products of filters ★

Author(s): Porton

Conjecture   for some filter objects , . Particularly, is this formula true for ?

A weaker conjecture:

Conjecture   for some filter objects , .

Keywords: filter products

## Barnette's Conjecture ★★★

Author(s): Barnette

Conjecture   Every 3-connected cubic planar bipartite graph is Hamiltonian.

Keywords: bipartite; cubic; hamiltonian

## Covering a square with unit squares ★★

Author(s):

Conjecture   For any integer , it is impossible to cover a square of side greater than with unit squares.

Keywords:

## Sequence defined on multisets ★★

Author(s): Erickson

Conjecture   Define a array of positive integers where the first row consists of some distinct positive integers arranged in increasing order, and the second row consists of any positive integers in any order. Create a new array where the first row consists of all the integers that occur in the first array, arranged in increasing order, and the second row consists of their multiplicities. Repeat the process. For example, starting with the array , the sequence is: -> -> -> -> -> -> -> -> -> -> -> , and we now have a fixed point (loop of one array).

The process always results in a loop of 1, 2, or 3 arrays.

Keywords: multiset; sequence

## Vertex Coloring of graph fractional powers ★★★

Conjecture   Let be a graph and be a positive integer. The power of , denoted by , is defined on the vertex set , by connecting any two distinct vertices and with distance at most . In other words, . Also subdivision of , denoted by , is constructed by replacing each edge of with a path of length . Note that for , we have .
Now we can define the fractional power of a graph as follows:
Let be a graph and . The graph is defined by the power of the subdivision of . In other words .
Conjecture. Let be a connected graph with and be a positive integer greater than 1. Then for any positive integer , we have .
In [1], it was shown that this conjecture is true in some special cases.

## Covering powers of cycles with equivalence subgraphs ★

Author(s):

Conjecture   Given and , the graph has equivalence covering number .

Keywords:

## Complexity of square-root sum ★★

Author(s): Goemans

Question   What is the complexity of the following problem?

Given , determine whether or not

Keywords: semi-definite programming