Variable degeneracy: Extensions of Brooks' and Gallai's theorems

O. V. Borodin, A. V. Kostochka, B. Toft

Research output: Contribution to journalArticlepeer-review

Abstract

We 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.

Original languageEnglish (US)
Pages (from-to)101-112
Number of pages12
JournalDiscrete Mathematics
Volume214
Issue number1-3
DOIs
StatePublished - Mar 21 2000
Externally publishedYes

Keywords

  • Degeneracy
  • Graph colouring
  • List colouring
  • Point partition numbers
  • Vertex function

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Variable degeneracy: Extensions of Brooks' and Gallai's theorems'. Together they form a unique fingerprint.

Cite this