Geometry » Polytopes

Cube-Simplex conjecture ★★★

Author(s): Kalai

Conjecture   For every positive integer $ k $, there exists an integer $ d $ so that every polytope of dimension $ \ge d $ has a $ k $-dimensional face which is either a simplex or is combinatorially isomorphic to a $ k $-dimensional cube.

Keywords: cube; facet; polytope; simplex

Posted by mdevos
updated May 9th, 2008
add new comment
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