Geometry

General position subsets ★★

Author(s): Gowers

Question   What is the least integer $ f(n) $ such that every set of at least $ f(n) $ points in the plane contains $ n $ collinear points or a subset of $ n $ points in general position (no three collinear)?

Keywords: general position subset, no-three-in-line problem

Posted by David Wood
updated March 24th, 2014
add new comment
Graph Theory » Coloring

Colouring $d$-degenerate graphs with large girth ★★

Author(s): Wood

Question   Does there exist a $ d $-degenerate graph with chromatic number $ d + 1 $ and girth $ g $, for all $ d \geq 2 $ and $ g \geq 3 $?

Keywords: degenerate; girth

Posted by David Wood
updated March 16th, 2014
add new comment
Graph Theory » Basic G.T. » Minors

Forcing a 2-regular minor ★★

Author(s): Reed; Wood

Conjecture   Every graph with average degree at least $ \frac{4}{3}t-2 $ contains every 2-regular graph on $ t $ vertices as a minor.

Keywords: minors

Posted by David Wood
updated March 16th, 2014
add new comment
Graph Theory

Fractional Hadwiger ★★

Author(s): Harvey; Reed; Seymour; Wood

Conjecture   For every graph $ G $,
(a) $ \chi_f(G)\leq\text{had}(G) $
(b) $ \chi(G)\leq\text{had}_f(G) $
(c) $ \chi_f(G)\leq\text{had}_f(G) $.

Keywords: fractional coloring, minors

Posted by David Wood
updated March 16th, 2014
add new comment