# On generalized list colourings of graphs

Mieczysław Borowiecki; Izak Broere; Peter Mihók

Discussiones Mathematicae Graph Theory (1997)

- Volume: 17, Issue: 1, page 127-132
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMieczysław Borowiecki, Izak Broere, and Peter Mihók. "On generalized list colourings of graphs." Discussiones Mathematicae Graph Theory 17.1 (1997): 127-132. <http://eudml.org/doc/270286>.

@article{MieczysławBorowiecki1997,

abstract = {
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 (𝓟,k)-choosability have been proved.
In this paper we prove some extensions of the well-known bounds for the 𝓟-chromatic number to the (𝓟,k)-choice number and then an extension of Brooks' theorem.
},

author = {Mieczysław Borowiecki, Izak Broere, Peter Mihók},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {hereditary property of graphs; list colouring; vertex partition number; -choosability; Brooks' theorem},

language = {eng},

number = {1},

pages = {127-132},

title = {On generalized list colourings of graphs},

url = {http://eudml.org/doc/270286},

volume = {17},

year = {1997},

}

TY - JOUR

AU - Mieczysław Borowiecki

AU - Izak Broere

AU - Peter Mihók

TI - On generalized list colourings of graphs

JO - Discussiones Mathematicae Graph Theory

PY - 1997

VL - 17

IS - 1

SP - 127

EP - 132

AB -
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 (𝓟,k)-choosability have been proved.
In this paper we prove some extensions of the well-known bounds for the 𝓟-chromatic number to the (𝓟,k)-choice number and then an extension of Brooks' theorem.

LA - eng

KW - hereditary property of graphs; list colouring; vertex partition number; -choosability; Brooks' theorem

UR - http://eudml.org/doc/270286

ER -

## References

top- [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. Zbl0902.05026
- [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. Zbl0845.05046
- [4] R.L. Brooks, On colouring the nodes of a network, Proc. Cambridge Phil. Soc. 37 (1941) 194-197, doi: 10.1017/S030500410002168X. Zbl0027.26403
- [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. Zbl0175.50505
- [6] G. Chartrand and L. Lesniak, Graphs and Digraphs, Second Edition, (Wadsworth & Brooks/Cole, Monterey, 1986). Zbl0666.05001
- [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. Zbl0046.41001
- [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. Zbl0144.23204
- [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. Zbl0871.05024
- [12] P. Mihók, An extension of Brooks' theorem, in: Proc. Fourth Czechoslovak Symp. on Combin., Combinatorics, Graphs, Complexity (Prague, 1991) 235-236. Zbl0766.05028
- [13] S.K. Stein, B-sets and planar graphs, Pacific J. Math. 37 (1971) 217-224. Zbl0194.56101
- [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).

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.