zbMATH — the first resource for mathematics

Variable degeneracy: Extensions of Brooks’ and Gallai’s theorems. (English) Zbl 0949.05029
Brooks’ theorem states that if \(G\) is a connected graph with maximum degree \(\Delta(G)= \Delta\geq 3\) and not the complete graph \(K_{\Delta+1}\), then its chromatic number \(\chi(G)\leq \Delta(G)\). (Reviewer’s remark: no reference is given to Brooks’ theorem; however, two references are given for an extension to Brooks’ theorem: one, in Russian, by one of the authors, and [B. Bollobás and B. Manvel, Optimal vertex partitions, Bull. Lond. Math. Soc. 11, 113-116 (1979; Zbl 0423.05021)].) Gallai’s theorem [T. Gallai, Kritische Graphen. I. Publ. Math. Inst. Hung. Acad. Sci., Ser. A 8, 165-192 (1963; Zbl 0121.18401)] states that in each \(k\)-colour-critical graph \(G\) every block of the subgraph \(H\) induced by the vertices of degree \(k-1\) is either a complete graph or an odd cycle.
Authors’ abstract (extended): We introduce the concept of variable degeneracy of a graph extending that of \(k\)-degeneracy (a graph \(G\) is said to be strictly \(k\)-degenerate if in every subgraph of \(G\) there is a vertex whose degree is less than \(k\)). This makes it possible to give a common generalization of the point partition numbers and the list chromatic number. In particular, the list point arboricity of a graph is considered. We extend Brooks’ and Gallai’s theorems in terms of covering the vertices of a graph by disjoint induced subgraphs \(G_1,\dots, G_s\) such that \(G_i\) is strictly \(f_i\)-degenerate, given nonnegative-integer-valued functions \(f_1,\dots, f_s\) whose sum is bounded below at each vertex by the degree of that vertex.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI