Home » Keyword index

girth


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 » Coloring » Vertex coloring

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

Posted by Andrew King
updated May 16th, 2020
1 comment
Graph Theory » Coloring

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

Posted by mdevos
updated January 29th, 2012
2 comments
Graph Theory » Coloring » Homomorphisms

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

Posted by mdevos
updated June 24th, 2007
add new comment
Syndicate content