Recent Activity

Edge-Colouring Geometric Complete Graphs ★★

Author(s): Hurtado

Question   What is the minimum number of colours such that every complete geometric graph on $ n $ 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 $ c $ such that every $ n $-vertex $ K_t $-minor-free graph has at most $ c^tn $ cliques?

Keywords: clique; graph; minor

A gold-grabbing game ★★

Author(s): Rosenfeld

Setup Fix a tree $ T $ and for every vertex $ v \in V(T) $ a non-negative integer $ g(v) $ which we think of as the amount of gold at $ v $.

2-Player game Players alternate turns. On each turn, a player chooses a leaf vertex $ v $ of the tree, takes the gold at this vertex, and then deletes $ v $. 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 $ {\mathcal O} $ denote the graph with vertex set consisting of all lines through the origin in $ {\mathbb R}^3 $ and two vertices adjacent in $ {\mathcal O} $ if they are perpendicular.

Problem   Is $ \chi_c({\mathcal O}) = 4 $?

Keywords: circular coloring; geometric graph; orthogonality

Crossing numbers and coloring ★★★

Author(s): Albertson

We let $ cr(G) $ denote the crossing number of a graph $ G $.

Conjecture   Every graph $ G $ with $ \chi(G) \ge t $ satisfies $ cr(G) \ge cr(K_t) $.

Keywords: coloring; complete graph; crossing number

Domination in cubic graphs ★★

Author(s): Reed

Problem   Does every 3-connected cubic graph $ G $ satisfy $ \gamma(G) \le \lceil |G|/3 \rceil $ ?

Keywords: cubic graph; domination

A generalization of Vizing's Theorem? ★★

Author(s): Rosenfeld

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

Keywords: edge-coloring; hypergraph; Vizing

Distribution and upper bound of mimic numbers ★★

Author(s): Bhattacharyya

Problem  

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

Definition   For any positive integer $ \mathcal{N} = \sum_{i=0}^{n}\mathcal{X}_{i}\mathcal{M}^{i} $ divisible by $ \mathcal{D} $, the mimic function, $ f(\mathcal{D} | \mathcal{N}) $, is given by,

$$ f(\mathcal{D} | \mathcal{N}) = \sum_{i=0}^{n}\mathcal{X}_{i}(\mathcal{M}-\mathcal{D})^{i} $$

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

Definition   The number $ m $ is defined to be the mimic number of any positive integer $ \mathcal{N} = \sum_{i=0}^{n}\mathcal{X}_{i}\mathcal{M}^{i} $, with respect to $ \mathcal{D} $, for the minimum value of which $ f^{m}(\mathcal{D} | \mathcal{N}) = \mathcal{D} $.

Given these two definitions and a positive integer $ \mathcal{D} $, find the distribution of mimic numbers of those numbers divisible by $ \mathcal{D} $.

Again, find whether there is an upper bound of mimic numbers for a set of numbers divisible by any fixed positive integer $ \mathcal{D} $.

Keywords: Divisibility; mimic function; mimic number

Coloring random subgraphs ★★

Author(s): Bukh

If $ G $ is a graph and $ p \in [0,1] $, we let $ G_p $ denote a subgraph of $ G $ where each edge of $ G $ appears in $ G_p $ with independently with probability $ p $.

Problem   Does there exist a constant $ c $ so that $ {\mathbb E}(\chi(G_{1/2})) > c \frac{\chi(G)}{\log \chi(G)} $?

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 $ {\mathcal F} $ of graphs is $ \chi $-bounded if there exists a function $ f: {\mathbb N} \rightarrow {\mathbb N} $ so that every $ G \in {\mathcal F} $ satisfies $ \chi(G) \le f (\omega(G)) $.

Conjecture   For every fixed tree $ T $, the family of graphs with no induced subgraph isomorphic to $ T $ is $ \chi $-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 $ k $ edges. Define a form parameter for a polyhedron as $ \beta:= v/(k+2) $ where $ v $ is the number of vertices. What is the distribution of $ \beta $ for $ k \to \infty $?

Keywords: polyhedral graphs, distribution

Domination in plane triangulations ★★

Author(s): Matheson; Tarjan

Conjecture   Every sufficiently large plane triangulation $ G $ has a dominating set of size $ \le \frac{1}{4} |V(G)| $.

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 $ \Delta $ has chromatic number at most $ \ceil{\frac{\Delta}{2}}+2 $.

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

Erdös-Szekeres conjecture ★★★

Author(s): Erdos; Szekeres

Conjecture   Every set of $ 2^{n-2} + 1 $ points in the plane in general position contains a subset of $ n $ points which form a convex $ n $-gon.

Keywords: combinatorial geometry; Convex Polygons; ramsey theory

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 $ n^n $ rectangular $ n $-dimensional boxes each of which has side lengths $ a_1,a_2,\ldots,a_n $ inside an $ n $-dimensional cube with side length $ a_1 + a_2 + \ldots a_n $?

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 $ X_1, \dotsc, X_n \geq 0 $ are independent random variables with $ \mathbb{E}[X_i] \leq \mu $, then $$\mathrm{Pr} \left( \sum X_i - \mathbb{E} \left[ \sum X_i \right ] < \delta \mu \right) \geq \min \left ( (1 + \delta)^{-1} \delta, e^{-1} \right).$$

Keywords: Inequality; Probability Theory; randomness in TCS

Grunbaum's Conjecture ★★★

Author(s): Grunbaum

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

Keywords: coloring; surface