On Extensions of a Conjecture of Gallai

A graphGisk-criticalif it has chromatic numberkbut every proper subgraph ofGhas a (k−1)-coloring. We prove the following result. IfGis ak-critical graph of ordern>k⩾3, thenGcontains fewer thann−3k/5+2 complete subgraphs of orderk−1.