Home » Keyword index

degenerate


Graph Theory » Coloring

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

Author(s): Wood

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 $?

Keywords: degenerate; girth

Posted by David Wood
updated March 16th, 2014
add new comment
Graph Theory » Topological G.T. » Coloring

Degenerate colorings of planar graphs ★★★

Author(s): Borodin

A graph $ G $ is $ k $-degenerate if every subgraph of $ G $ has a vertex of degree $ \le k $.

Conjecture   Every simple planar graph has a 5-coloring so that for $ 1 \le k \le 4 $, the union of any $ k $ color classes induces a $ (k-1) $-degenerate graph.

Keywords: coloring; degenerate; planar

Posted by mdevos
updated May 21st, 2008
add new comment
Syndicate content