Combinatorics

Monotone 4-term Arithmetic Progressions ★★

Author(s): Davis; Entringer; Graham; Simmons

Question   Is it true that every permutation of positive integers must contain monotone 4-term arithmetic progressions?

Keywords: monotone arithmetic progression; permutation

Posted by vjungic
updated October 3rd, 2007
add new comment
Graph Theory » Coloring » Vertex coloring

Coloring the Odd Distance Graph ★★★

Author(s): Rosenfeld

The Odd Distance Graph, denoted $ {\mathcal O} $, is the graph with vertex set $ {\mathbb R}^2 $ and two points adjacent if the distance between them is an odd integer.

Question   Is $ \chi({\mathcal O}) = \infty $?

Keywords: coloring; geometric graph; odd distance

Posted by mdevos
updated March 19th, 2012
8 comments
Graph Theory » Directed Graphs

The Bermond-Thomassen Conjecture ★★

Author(s): Bermond; Thomassen

Conjecture   For every positive integer $ k $, every digraph with minimum out-degree at least $ 2k-1 $ contains $ k $ disjoint cycles.

Keywords: cycles

Posted by JS
updated October 1st, 2007
add new comment