Home » Author index

Albertson, Michael O.


Graph Theory » Topological G.T. » Crossing numbers

Crossing numbers and coloring ★★★

Author(s): Albertson

We let $ cr(G) $ denote the crossing number of a graph $ G $.

Conjecture   Every graph $ G $ with $ \chi(G) \ge t $ satisfies $ cr(G) \ge cr(K_t) $.

Keywords: coloring; complete graph; crossing number

Posted by mdevos
updated September 4th, 2009
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
Syndicate content