Graph Theory » Coloring » Vertex coloring

List Colourings of Complete Multipartite Graphs with 2 Big Parts ★★

Author(s): Allagan

Question   Given $ a,b\geq2 $, what is the smallest integer $ t\geq0 $ such that $ \chi_\ell(K_{a,b}+K_t)= \chi(K_{a,b}+K_t) $?

Keywords: complete bipartite graph; complete multipartite graph; list coloring

Posted by Jon Noel
updated April 12th, 2014
add new comment
Geometry

Geometric Hales-Jewett Theorem ★★

Author(s): Por; Wood

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:
    \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)

Keywords: Hales-Jewett Theorem; ramsey theory

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

Generalised Empty Hexagon Conjecture ★★

Author(s): Wood

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.

Keywords: empty hexagon

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