Graph Theory » Coloring » Vertex coloring

Partial List Coloring ★★★

Author(s): Albertson; Grossman; Haas

Conjecture   Let $ G $ be a simple graph with $ n $ vertices and list chromatic number $ \chi_\ell(G) $. Suppose that $ 0\leq t\leq \chi_\ell $ and each vertex of $ G $ is assigned a list of $ t $ colors. Then at least $ \frac{tn}{\chi_\ell(G)} $ vertices of $ G $ can be colored from these lists.

Keywords: list assignment; list coloring

Posted by Iradmusa
updated May 5th, 2008
add new comment
Combinatorics » Designs

Combinatorial covering designs ★

Author(s): Gordon; Mills; Rödl; Schönheim

A $ (v, k, t) $ covering design, or covering, is a family of $ k $-subsets, called blocks, chosen from a $ v $-set, such that each $ t $-subset is contained in at least one of the blocks. The number of blocks is the covering’s size, and the minimum size of such a covering is denoted by $ C(v, k, t) $.

Problem   Find a closed form, recurrence, or better bounds for $ C(v,k,t) $. Find a procedure for constructing minimal coverings.

Keywords: recreational mathematics

Posted by Pseudonym
updated April 11th, 2008
add new comment
Group Theory

Burnside problem ★★★★

Author(s): Burnside

Conjecture   If a group has $ r $ generators and exponent $ n $, is it necessarily finite?

Keywords:

Posted by dlh12
updated April 11th, 2008
add new comment
Topology

Inscribed Square Problem ★★

Author(s): Toeplitz

Conjecture   Does every Jordan curve have 4 points on it which form the vertices of a square?

Keywords: simple closed curve; square

Posted by dlh12
updated February 25th, 2021
8 comments