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

Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★

Author(s): Kostochka; Reed

Conjecture   A triangle-free graph with maximum degree $ \Delta $ has chromatic number at most $ \ceil{\frac{\Delta}{2}}+2 $.

Keywords: chromatic number; girth; maximum degree; triangle free

4-regular 4-chromatic graphs of high girth ★★

Author(s): Grunbaum

Problem   Do there exist 4-regular 4-chromatic graphs of arbitrarily high girth?

Keywords: coloring; girth

Mapping planar graphs to odd cycles ★★★

Author(s): Jaeger

Conjecture   Every planar graph of girth $ \ge 4k $ has a homomorphism to $ C_{2k+1} $.

Keywords: girth; homomorphism; planar graph

Syndicate content