Wood, David R.

Chromatic number of associahedron ★★

Author(s): Fabila-Monroy; Flores-Penaloza; Huemer; Hurtado; Urrutia; Wood

\begin{conjecture} Associahedra have unbounded chromatic number. \end{conjecture}

Keywords: associahedron, graph colouring, chromatic number

Geometric Hales-Jewett Theorem ★★

Author(s): Por; Wood

\begin{conjecture} For all integers $k\geq1$ and $\ell\geq3$, there is an integer $f(k,\ell)$ such that for every set $P$ of at least $f(k,\ell)$ points in the plane, if each point in $P$ is assigned one of $k$ colours, then: \begin{itemize} \item $P$ contains $\ell$ collinear points, or \item $P$ contains a monochromatic line (that is, a maximal set of collinear points receiving the same colour) \end{itemize} \end{conjecture}

Keywords: Hales-Jewett Theorem; ramsey theory

Generalised Empty Hexagon Conjecture ★★

Author(s): Wood

\begin{conjecture} For each $\ell\geq3$ there is an integer $f(\ell)$ such that every set of at least $f(\ell)$ points in the plane contains $\ell$ collinear points or an empty hexagon. \end{conjecture}

Keywords: empty hexagon

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

Author(s): Wood

\begin{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$? \end{question}

Keywords: degenerate; girth

Forcing a 2-regular minor ★★

Author(s): Reed; Wood

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

Keywords: minors

Fractional Hadwiger ★★

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

\begin{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)$. \end{conjecture}

Keywords: fractional coloring, minors

Forcing a $K_6$-minor ★★

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

\begin{conjecture} Every graph with minimum degree at least 7 contains a $K_6$-minor. \end{conjecture}

\begin{conjecture} Every 7-connected graph contains a $K_6$-minor. \end{conjecture}

Keywords: connectivity; graph minors

Point sets with no empty pentagon

Author(s): Wood

\begin{problem} Classify the point sets with no empty pentagon. \end{problem}

Keywords: combinatorial geometry; visibility graph

Number of Cliques in Minor-Closed Classes ★★

Author(s): Wood

\begin{question} Is there a constant $c$ such that every $n$-vertex $K_t$-minor-free graph has at most $c^tn$ cliques? \end{question}

Keywords: clique; graph; minor

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 \emph{visible} with respect to $S$ if the line segment between $v$ and $w$ contains no other point in $S$.

\begin{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. \end{conjecture}

Keywords: Discrete Geometry; Geometric Ramsey Theory

Syndicate content