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

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

doi:10.1016/S0012-365X(99)00221-6

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

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

Research output: Contribution to journal › Article › peer-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 G₁,...,G_s such that G_i is strictly f_i-degenerate, given nonnegative-integer-valued functions f₁,...,f_s whose sum is bounded below at each vertex by the degree of that vertex.

Original language	English (US)
Pages (from-to)	101-112
Number of pages	12
Journal	Discrete Mathematics
Volume	214
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(99)00221-6
State	Published - Mar 21 2000
Externally published	Yes

Keywords

Degeneracy
Graph colouring
List colouring
Point partition numbers
Vertex function

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1016/S0012-365X(99)00221-6

Library availability

Discover UIUC Full Text

Cite this

@article{69b7e21ad8a6431ea1b66ba8521039b5,

title = "Variable degeneracy: Extensions of Brooks' and Gallai's theorems",

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.",

keywords = "Degeneracy, Graph colouring, List colouring, Point partition numbers, Vertex function",

author = "Borodin, {O. V.} and Kostochka, {A. V.} and B. Toft",

note = "Funding Information: ∗Corresponding author. E-mail address: brdnoleg@math.nsc.ru (O.V. Borodin) 1This work was partially supported by the Network DIMANET of the European Union and the grant NQ4300 of International Science Foundation and Russian Government. 2This work was partially supported by the grant 96-01-01614 of the Russian Foundation for Fundamental Research and the grant RPY300 of International Science Foundation and Russian Government. 3This work was partially supported by the grant for discrete mathematics of the Danish Natural Science Research Council.",

year = "2000",

month = mar,

day = "21",

doi = "10.1016/S0012-365X(99)00221-6",

language = "English (US)",

volume = "214",

pages = "101--112",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Variable degeneracy

T2 - Extensions of Brooks' and Gallai's theorems

AU - Borodin, O. V.

AU - Kostochka, A. V.

AU - Toft, B.

N1 - Funding Information: ∗Corresponding author. E-mail address: brdnoleg@math.nsc.ru (O.V. Borodin) 1This work was partially supported by the Network DIMANET of the European Union and the grant NQ4300 of International Science Foundation and Russian Government. 2This work was partially supported by the grant 96-01-01614 of the Russian Foundation for Fundamental Research and the grant RPY300 of International Science Foundation and Russian Government. 3This work was partially supported by the grant for discrete mathematics of the Danish Natural Science Research Council.

PY - 2000/3/21

Y1 - 2000/3/21

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

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

KW - Degeneracy

KW - Graph colouring

KW - List colouring

KW - Point partition numbers

KW - Vertex function

UR - http://www.scopus.com/inward/record.url?scp=0347647633&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0347647633&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(99)00221-6

DO - 10.1016/S0012-365X(99)00221-6

M3 - Article

AN - SCOPUS:0347647633

SN - 0012-365X

VL - 214

SP - 101

EP - 112

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this