DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 15(2) (1995) 185-193
DOI: 10.7151/dmgt.1016

GENERALIZED LIST COLOURINGS OF GRAPHS

Mieczysław Borowiecki
Ewa Drgas-Burchardt

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

Peter Mihók

Department of Geometry and Algebra
P.J. Šafárik University
041 54 Košice, Slovakia

Abstract

We prove: (1) that chP(G)-χP(G) can be arbitrarily large, where chP(G) and χP(G) are P-choice and P-chromatic numbers, respectively, (2) the (P,L)-colouring version of Brooks' and Gallai's theorems.

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

1991 Mathematics Subject Classification: 05C15, 05C70.

References

[1] M. Borowiecki and P. Mihók, Hereditary Properties of Graphs, in: Advances in Graph Theory (Vishwa International Publications, 1991) 41-68.
[2] R.L. Brooks, On colouring the nodes of a network, Proc. Cambridge Phil. Soc. 37 (1941) 194-197, doi: 10.1017/S030500410002168X.
[3] 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.
[4] T. Gallai, Kritiche Graphen I, Publ. Math. Inst. Hung. Acad. Sci. 8 (1963) 373-395.
[5] F. Harary, Graph Theory (Addison Wesley, Reading, Mass. 1969).
[6] V.G. Vizing, Colouring the vertices of a graph in prescribed colours (in Russian), Diskret. Analiz 29 (1976) 3-10.