# Recent Activity

## Are different notions of the crossing number the same? ★★★

Author(s): Pach; Tóth

Problem   Does the following equality hold for every graph ?

The crossing number of a graph is the minimum number of edge crossings in any drawing of in the plane. In the pairwise crossing number , we minimize the number of pairs of edges that cross.

Keywords: crossing number; pair-crossing number

## Shuffle-Exchange Conjecture (graph-theoretic form) ★★★

Author(s): Beneš; Folklore; Stone

Given integers , the 2-stage Shuffle-Exchange graph/network, denoted , is the simple -regular bipartite graph with the ordered pair of linearly labeled parts and , where , such that vertices and are adjacent if and only if (see Fig.1).

Given integers , the -stage Shuffle-Exchange graph/network, denoted , is the proper (i.e., respecting all the orders) concatenation of identical copies of (see Fig.1).

Let be the smallest integer such that the graph is rearrangeable.

Problem   Find .
Conjecture   .

Keywords:

## Partition of Complete Geometric Graph into Plane Trees ★★

Author(s):

Conjecture   Every complete geometric graph with an even number of vertices has a partition of its edge set into plane (i.e. non-crossing) spanning trees.

## Edge-Colouring Geometric Complete Graphs ★★

Question   What is the minimum number of colours such that every complete geometric graph on vertices has an edge colouring such that:
\item[Variant A] crossing edges get distinct colours, \item[Variant B] disjoint edges get distinct colours, \item[Variant C] non-disjoint edges get distinct colours, \item[Variant D] non-crossing edges get distinct colours.

Keywords: geometric complete graph, colouring

## Number of Cliques in Minor-Closed Classes ★★

Author(s): Wood

Question   Is there a constant such that every -vertex -minor-free graph has at most cliques?

Keywords: clique; graph; minor

## A gold-grabbing game ★★

Author(s): Rosenfeld

Setup Fix a tree and for every vertex a non-negative integer which we think of as the amount of gold at .

2-Player game Players alternate turns. On each turn, a player chooses a leaf vertex of the tree, takes the gold at this vertex, and then deletes . The game ends when the tree is empty, and the winner is the player who has accumulated the most gold.

Problem   Find optimal strategies for the players.

Keywords: game; tree

## Circular colouring the orthogonality graph ★★

Author(s): DeVos; Ghebleh; Goddyn; Mohar; Naserasr

Let denote the graph with vertex set consisting of all lines through the origin in and two vertices adjacent in if they are perpendicular.

Problem   Is ?

## Crossing numbers and coloring ★★★

Author(s): Albertson

We let denote the crossing number of a graph .

Conjecture   Every graph with satisfies .

Keywords: coloring; complete graph; crossing number

## Domination in cubic graphs ★★

Author(s): Reed

Problem   Does every 3-connected cubic graph satisfy ?

Keywords: cubic graph; domination

## A generalization of Vizing's Theorem? ★★

Author(s): Rosenfeld

Conjecture   Let be a simple -uniform hypergraph, and assume that every set of points is contained in at most edges. Then there exists an -edge-coloring so that any two edges which share vertices have distinct colors.

Keywords: edge-coloring; hypergraph; Vizing

## Distribution and upper bound of mimic numbers ★★

Author(s): Bhattacharyya

Problem

Let the notation denote '' divides ''. The mimic function in number theory is defined as follows [1].

Definition   For any positive integer divisible by , the mimic function, , is given by,

By using this definition of mimic function, the mimic number of any non-prime integer is defined as follows [1].

Definition   The number is defined to be the mimic number of any positive integer , with respect to , for the minimum value of which .

Given these two definitions and a positive integer , find the distribution of mimic numbers of those numbers divisible by .

Again, find whether there is an upper bound of mimic numbers for a set of numbers divisible by any fixed positive integer .

Keywords: Divisibility; mimic function; mimic number

## Coloring random subgraphs ★★

Author(s): Bukh

If is a graph and , we let denote a subgraph of where each edge of appears in with independently with probability .

Problem   Does there exist a constant so that ?

Keywords: coloring; random graph

## Are vertex minor closed classes chi-bounded? ★★

Author(s): Geelen

Question   Is every proper vertex-minor closed class of graphs chi-bounded?

Keywords: chi-bounded; circle graph; coloring; vertex minor

## Graphs with a forbidden induced tree are chi-bounded ★★★

Author(s): Gyarfas

Say that a family of graphs is -bounded if there exists a function so that every satisfies .

Conjecture   For every fixed tree , the family of graphs with no induced subgraph isomorphic to is -bounded.

Keywords: chi-bounded; coloring; excluded subgraph; tree

## Asymptotic Distribution of Form of Polyhedra ★★

Author(s): Rüdinger

Problem   Consider the set of all topologically inequivalent polyhedra with edges. Define a form parameter for a polyhedron as where is the number of vertices. What is the distribution of for ?

Keywords: polyhedral graphs, distribution

## Domination in plane triangulations ★★

Author(s): Matheson; Tarjan

Conjecture   Every sufficiently large plane triangulation has a dominating set of size .

Keywords: coloring; domination; multigrid; planar graph; triangulation

## Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★

Author(s): Kostochka; Reed

Conjecture   A triangle-free graph with maximum degree has chromatic number at most .

Keywords: chromatic number; girth; maximum degree; triangle free

## Erdös-Szekeres conjecture ★★★

Author(s): Erdos; Szekeres

Conjecture   Every set of points in the plane in general position contains a subset of points which form a convex -gon.

## 4-flow conjecture ★★★

Author(s): Tutte

Conjecture   Every bridgeless graph with no Petersen minor has a nowhere-zero 4-flow.

Keywords: minor; nowhere-zero flow; Petersen graph

## Inequality of the means ★★★

Author(s):

Question   Is is possible to pack rectangular -dimensional boxes each of which has side lengths inside an -dimensional cube with side length ?

Keywords: arithmetic mean; geometric mean; Inequality; packing