![](/files/happy5.png)
degenerate
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
Degenerate colorings of planar graphs ★★★
Author(s): Borodin
A graph is
-degenerate if every subgraph of
has a vertex of degree
.
Conjecture Every simple planar graph has a 5-coloring so that for
, the union of any
color classes induces a
-degenerate graph.
![$ 1 \le k \le 4 $](/files/tex/8444626f9ce5a1ce2947ad77497c0627b390df33.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ (k-1) $](/files/tex/bc98477dfed13603bd35290b8c8d5cd9c5af536f.png)
Keywords: coloring; degenerate; planar
![Syndicate content Syndicate content](/misc/feed.png)