Home » Author index

Wood, David R.


Graph Theory » Basic G.T. » Minors

Forcing a $K_6$-minor ★★

Author(s): Barát ; Joret; Wood

Conjecture   Every graph with minimum degree at least 7 contains a $ K_6 $-minor.
Conjecture   Every 7-connected graph contains a $ K_6 $-minor.

Keywords: connectivity; graph minors

Posted by David Wood
updated January 16th, 2012
add new comment
Geometry

Point sets with no empty pentagon ★

Author(s): Wood

Problem   Classify the point sets with no empty pentagon.

Keywords: combinatorial geometry; visibility graph

Posted by David Wood
updated December 14th, 2010
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 » Topological G.T. » Drawings

Compatible Matching Conjecture ★★

Author(s): Wood

For an even set $ S $ of points in the plane, a perfect matching of $ S $ is a collection of nonintersecting segments such that every point of $ S $ is an end of exactly one of the segments.

Conjecture   Let $ S $ be a set of points in the plane in general position such that $ |S| $ is divisible by 4. Then for every perfect matching $ M $ of $ S $ there is another perfect matching, $ N $, of $ S $ such that no segment of $ M $ crosses a segment of $ N $.

Keywords: geometric graphs; matchings

Posted by Robert Samal
updated July 31st, 2008
add new comment
Geometry

Big Line or Big Clique in Planar Point Sets ★★

Author(s): Kara; Por; Wood

Let $ S $ be a set of points in the plane. Two points $ v $ and $ w $ in $ S $ are visible with respect to $ S $ if the line segment between $ v $ and $ w $ contains no other point in $ S $.

Conjecture   For all integers $ k,\ell\geq2 $ there is an integer $ n $ such that every set of at least $ n $ points in the plane contains at least $ \ell $ collinear points or $ k $ pairwise visible points.

Keywords: Discrete Geometry; Geometric Ramsey Theory

Posted by David Wood
updated September 25th, 2012
1 comment
Syndicate content