![](/files/happy5.png)
girth
Colouring $d$-degenerate graphs with large girth ★★
Author(s): Wood
Question Does there exist a
-degenerate graph with chromatic number
and girth
, for all
and
?
![$ d $](/files/tex/aeba4a4076fc495e8b5df04d874f2911a838883a.png)
![$ d + 1 $](/files/tex/2b7e8b22bf0d4e0aa6cc7dcc6acf051bab97990f.png)
![$ g $](/files/tex/4239ee4145983e1d8ad375f0606cc7140bce36a3.png)
![$ d \geq 2 $](/files/tex/6dfe01f1d81a75b84c1284e30c319cc6137173b1.png)
![$ g \geq 3 $](/files/tex/58bd309cb5a84dc6bb041e8d02207c64d974c46d.png)
Keywords: degenerate; girth
Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★
Conjecture A triangle-free graph with maximum degree
has chromatic number at most
.
![$ \Delta $](/files/tex/e3f8e135c571143e94f1d4f236326b862080b200.png)
![$ \ceil{\frac{\Delta}{2}}+2 $](/files/tex/522a3a86b51cce46cfcff77891e669d1b9ff9147.png)
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?
Mapping planar graphs to odd cycles ★★★
Author(s): Jaeger
Conjecture Every planar graph of girth
has a homomorphism to
.
![$ \ge 4k $](/files/tex/cf3c6265929d41a26d0297d4ba26c602e0e2d93b.png)
![$ C_{2k+1} $](/files/tex/f20c34c1abcdfc50a63f8c5920f0ddb51a9f7cae.png)
Keywords: girth; homomorphism; planar graph
![Syndicate content Syndicate content](/misc/feed.png)