degenerate


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

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

Syndicate content