Section 1.10: Generalized Graph Coloring
Theorem 39 (Bollobás and Manvel 1979) was obtained independently
by Oleg V. Borodin, Russian Academy of Sciences, Novosibirsk,
in his paper "On decomposing graphs into degenerate subgraphs"
(in Russian), Metody Diskret Analiz. 28, 3-11, 1976, and in his
Ph.D.-thesis Problems of Graph Colouring and of Covering the
Vertex Set of a Graph with Induced Subgraphs (in Russian),
Novosibirsk 1979.
The 1976 paper contained the theorem in part. With the
same assumption as in Theorem 39 that pq>1 (or p+q>2) Borodin
proved in Theorem I of the paper (page 5) that
Sp+q
∩
Ip+q-1
⊆
Cp-1 Cq-1.
This is the part of Theorem 39 that implies Brooks' Theorem
as explained on page 23 of "Graph Coloring Problems".
In the 1979 Ph.D.-thesis Borodin obtained the Bollobás-Manvel
Theorem in full (Theorem 2.I of the thesis).
We are grateful to Oleg V. Borodin for relaying this information
to us in November 1994 during his visit to Odense University,
Denmark.
December 16, 1994 T.R. Jensen and B. Toft.
Last modified July 21, 1997 Bjarne Toft