Brooksʼ Theorem for generalized dart graphs

The well-known Brooksʼ Theorem says that each graph G   of maximum degree k⩾3k⩾3 is k  -colorable unless G=Kk+1G=Kk+1. We generalize this theorem by allowing higher degree vertices with prescribed types of neighborhood.

► Generalization of Brooks Theorem for (k,s)(k,s)-dart graphs. ► Linear algorithm for (k+1)(k+1)-coloring of (k,s)(k,s)-dart graphs with s not greater then k  . ► NP-completeness for (k+1)(k+1)-coloring of (k,s)(k,s)-dart graphs with s greater then k.