# Recent Activity

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

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

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

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

Keywords: combinatorial geometry; Convex Polygons; ramsey theory

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

## P vs. PSPACE ★★★

Author(s): Folklore

**Problem**Is there a problem that can be computed by a Turing machine in polynomial space and unbounded time but not in polynomial time? More formally, does P = PSPACE?

Keywords: P; PSPACE; separation; unconditional

## Sums of independent random variables with unbounded variance ★★

Author(s): Feige

**Conjecture**If are independent random variables with , then

Keywords: Inequality; Probability Theory; randomness in TCS

## Grunbaum's Conjecture ★★★

Author(s): Grunbaum

**Conjecture**If is a simple loopless triangulation of an orientable surface, then the dual of is 3-edge-colorable.

## Refuting random 3SAT-instances on $O(n)$ clauses (weak form) ★★★

Author(s): Feige

**Conjecture**For every rational and every rational , there is no polynomial-time algorithm for the following problem.

Given is a 3SAT (3CNF) formula on variables, for some , and clauses drawn uniformly at random from the set of formulas on variables. Return with probability at least 0.5 (over the instances) that is *typical* without returning *typical* for *any* instance with at least simultaneously satisfiable clauses.

Keywords: NP; randomness in TCS; satisfiability

## Does the chromatic symmetric function distinguish between trees? ★★

Author(s): Stanley

**Problem**Do there exist non-isomorphic trees which have the same chromatic symmetric function?

Keywords: chromatic polynomial; symmetric function; tree

## Shannon capacity of the seven-cycle ★★★

Author(s):

**Problem**What is the Shannon capacity of ?

Keywords:

## Book Thickness of Subdivisions ★★

Author(s): Blankenship; Oporowski

Let be a finite undirected simple graph.

A *-page book embedding* of consists of a linear order of and a (non-proper) -colouring of such that edges with the same colour do not cross with respect to . That is, if for some edges , then and receive distinct colours.

One can think that the vertices are placed along the spine of a book, and the edges are drawn without crossings on the pages of the book.

The *book thickness* of , denoted by bt is the minimum integer for which there is a -page book embedding of .

Let be the graph obtained by subdividing each edge of exactly once.

**Conjecture**There is a function such that for every graph ,

Keywords: book embedding; book thickness

## Frobenius number of four or more integers ★★

Author(s):

**Problem**Find an explicit formula for Frobenius number of co-prime positive integers for .

Keywords:

## Magic square of squares ★★

Author(s): LaBar

**Question**Does there exist a magic square composed of distinct perfect squares?

Keywords: