Variable degeneracy: extensions of Brooks’ and Gallai's theorems
2000; Elsevier BV; Volume: 214; Issue: 1-3 Linguagem: Inglês
10.1016/s0012-365x(99)00221-6
ISSN1872-681X
AutoresO. V. Borodin, Alexandr Kostochka, Bjarne Toft,
Tópico(s)Graph Labeling and Dimension Problems
ResumoWe introduce the concept of variable degeneracy of a graph extending that of k-degeneracy. 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 G1,…,Gs such that Gi is strictly fi-degenerate, given nonnegative-integer-valued functions f1,…,fs whose sum is bounded below at each vertex by the degree of that vertex.
Referência(s)