ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory  17(1) (1997)   127-132
DOI: 10.7151/dmgt.1045


Mieczysław Borowiecki

Institute of Mathematics
Technical University of Zielona Góra
Podgórna 50, 65-246 Zielona Góra, Poland

Izak Broere

Department of Mathematics
Rand Afrikaans University
P.O. Box 524, Auckland Park, 2006 South Africa

Peter Mihók

Mathematical Institute of Slovak Academy of Sciences
Grešákova 6, 040 01 Košice, Slovakia
e-mail: mihok@Koš


Vizing [15] and Erdős et al. [8] independently introduce the idea of considering list-colouring and k-choosability. In the both papers the choosability version of Brooks' theorem [4] was proved but the choosability version of Gallai's theorem [9] was proved independently by Thomassen [14] and by Kostochka et al. [11]. In [3] some extensions of these two basic theorems to (P,k)-choosability have been proved.

In this paper we prove some extensions of the well-known bounds for the P-chromatic number to the (P,k)-choice number and then an extension of Brooks' theorem.

Keywords: hereditary property of graphs, list colouring, vertex partition number.

1991 Mathematics Subject Classification: 05C15, 05C70.


[1] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discussiones Mathematicae Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037.
[2] M. Borowiecki and P. Mihók, Hereditary Properties of Graphs, in: Advances in Graph Theory (Vishwa International Publications, 1991) 41-68.
[3] M. Borowiecki, E. Drgas-Burchardt, Generalized list colourings of graphs, Discussiones Math. Graph Theory 15 (1995) 185-193, doi: 10.7151/dmgt.1016.
[4] R.L. Brooks, On colouring the nodes of a network, Proc. Cambridge Phil. Soc. 37 (1941) 194-197, doi: 10.1017/S030500410002168X.
[5] G. Chartrand and H.H. Kronk, The point arboricity of planar graphs, J. London Math. Soc. 44 (1969) 612-616, doi: 10.1112/jlms/s1-44.1.612.
[6] G. Chartrand and L. Lesniak, Graphs and Digraphs, Second Edition, (Wadsworth & Brooks/Cole, Monterey, 1986).
[7] G. Dirac, A property of 4-chromatic graphs and remarks on critical graphs, J. London Math. Soc. 27 (1952) 85-92, doi: 10.1112/jlms/s1-27.1.85.
[8] P. Erdős, A.L. Rubin and H. Taylor, Choosability in graphs, in: Proc. West Coast Conf. on Combin., Graph Theory and Computing, Congressus Numerantium XXVI (1979) 125-157.
[9] T. Gallai, Kritiche Graphen I, Publ. Math. Inst. Hung. Acad. Sci. 8 (1963) 373-395.
[10] T.R. Jensen and B. Toft, Graph Colouring Problems, (Wiley-Interscience Publications, New York, 1995).
[11] A.V. Kostochka, M. Stiebitz and B. Wirth, The colour theorems of Brooks and Gallai extended, Discrete Math. 162 (1996) 299-303, doi: 10.1016/0012-365X(95)00294-7.
[12] P. Mihók, An extension of Brooks' theorem, in: Proc. Fourth Czechoslovak Symp. on Combin., Combinatorics, Graphs, Complexity (Prague, 1991) 235-236.
[13] S.K. Stein, B-sets and planar graphs, Pacific J. Math. 37 (1971) 217-224.
[14] C. Thomassen, Color-critical graphs on a fixed surface (Report, Technical University of Denmark, Lyngby, 1995).
[15] V.G. Vizing, Colouring the vertices of a graph in prescribed colours, Diskret. Analiz 29 (1976) 3-10 (in Russian).