Recent Activity

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

Given integers $k,n \ge 2$ , the 2-stage Shuffle-Exchange graph/network, denoted $\text{SE}(k,n)$ , is the simple $k$ -regular bipartite graph with the ordered pair $(U,V)$ of linearly labeled parts $U:=\{u_0,\dots,u_{t-1}\}$ and $V:=\{v_0,\dots,v_{t-1}\}$ , where $t:=k^{n-1}$ , such that vertices $u_i$ and $v_j$ are adjacent if and only if $(j - ki) \text{ mod } t < k$ (see Fig.1).

Given integers $k,n,r \ge 2$ , the $r$ -stage Shuffle-Exchange graph/network, denoted $(\text{SE}(k,n))^{r-1}$ , is the proper (i.e., respecting all the orders) concatenation of $r-1$ identical copies of $\text{SE}(k,n)$ (see Fig.1).

Let $r(k,n)$ be the smallest integer $r\ge 2$ such that the graph $(\text{SE}(k,n))^{r-1}$ is rearrangeable.

Problem Find $r(k,n)$ .

Conjecture $r(k,n)=2n-1$ .

Keywords:

Posted by Vadim Lioubimov
updated October 30th, 2009

add new comment

Geometry

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

Posted by David Wood
updated October 19th, 2009

add new comment

Graph Theory

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

Posted by David Wood
updated October 12th, 2009

add new comment

Graph Theory » Graph Algorithms

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

Posted by mdevos
updated October 4th, 2009

1 comment

Graph Theory » Coloring » Vertex coloring

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

Posted by mdevos
updated September 28th, 2009

4 comments

Graph Theory » Topological G.T. » Crossing numbers

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

Posted by mdevos
updated September 4th, 2009

add new comment

Graph Theory » Basic G.T.

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

Posted by mdevos
updated August 19th, 2009

add new comment

Graph Theory » Coloring » Edge coloring

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

Posted by mdevos
updated June 23rd, 2009

1 comment

Number Theory » Analytic N.T.

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

Posted by facility_cttb@i...
updated June 20th, 2009

add new comment

Graph Theory » Probabilistic G.T.

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

Posted by mdevos
updated June 4th, 2009

1 comment

Graph Theory » Coloring » Vertex coloring

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

Posted by mdevos
updated May 16th, 2009

add new comment

Graph Theory » Coloring » Vertex coloring

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

Posted by mdevos
updated May 16th, 2009

add new comment

Graph Theory » Basic G.T.

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

Posted by andreasruedinger
updated May 9th, 2009

add new comment

Graph Theory » Topological G.T.

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

Posted by mdevos
updated May 4th, 2009

add new comment

Geometry

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

Posted by mdevos
updated April 14th, 2009

1 comment

Graph Theory » Coloring » Nowhere-zero flows

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

Posted by mdevos
updated April 12th, 2009

2 comments

Geometry

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

Posted by mdevos
updated April 6th, 2009

add new comment

Theoretical Comp. Sci. » Complexity

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

Posted by cwenner
updated April 4th, 2009

add new comment

Theoretical Comp. Sci.

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).$