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

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

Keywords: Inequality; Probability Theory; randomness in TCS

Posted by cwenner
updated April 2nd, 2009

add new comment

Graph Theory » Topological G.T. » Coloring

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

Posted by mdevos
updated March 23rd, 2009

5 comments

Theoretical Comp. Sci. » Complexity » Hardness of Approximation

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

Author(s): Feige

Conjecture For every rational $\epsilon > 0$ and every rational $\Delta$ , there is no polynomial-time algorithm for the following problem.

Given is a 3SAT (3CNF) formula $I$ on $n$ variables, for some $n$ , and $m = \floor{\Delta n}$ clauses drawn uniformly at random from the set of formulas on $n$ variables. Return with probability at least 0.5 (over the instances) that $I$ is typical without returning typical for any instance with at least $(1 - \epsilon)m$ simultaneously satisfiable clauses.