Graph Theory » Coloring » Vertex coloring

Bounding the chromatic number of graphs with no odd hole ★★★

Author(s): Gyarfas

Conjecture   There exists a fixed function $ f : {\mathbb N} \rightarrow {\mathbb N} $ so that $ \chi(G) \le f(\omega(G)) $ for every graph $ G $ with no odd hole.

Keywords: chi-bounded; coloring; induced subgraph; odd hole; perfect graph

Posted by mdevos
updated June 25th, 2007
add new comment
Number Theory

Lonely runner conjecture ★★★

Author(s): Cusick; Wills

Conjecture   Suppose $ k $ runners having distinct constant speeds start at a common point and run laps on a circular track with circumference 1. Then for any given runner, there is a time at which that runner is distance at least $ \frac{1}{k} $ (along the track) away from every other runner.

Keywords: diophantine approximation; view obstruction

Posted by mdevos
updated June 24th, 2007
add new comment
Number Theory » Combinatorial N.T.

Sets with distinct subset sums ★★★

Author(s): Erdos

Say that a set $ S \subseteq {\mathbb Z} $ has distinct subset sums if distinct subsets of $ S $ have distinct sums.

Conjecture   There exists a fixed constant $ c $ so that $ |S| \le \log_2(n) + c $ whenever $ S \subseteq \{1,2,\ldots,n\} $ has distinct subset sums.

Keywords: subset sum

Posted by mdevos
updated April 7th, 2011
1 comment