Home » Keyword index

maximum degree


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
Syndicate content