Open Problem Garden

geometric complete graph, colouring

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

clique

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

game

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 » Topological G.T. » Crossing numbers