Download PDF - Generalized list colourings of graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Generalized list colourings of graphs

Authors 1, 1, 2

Affiliations

  1. Institute of Mathematics, Technical University
  2. Department of Geometry and Algebra, P.J. Šafárik University

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

ENG
hereditary property of graphs, list colouring, vertex partition number

Bibliography

  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.
Discussiones Mathematicae Graph Theory
1995/15/2
Export to PBN, Opens in new tab
Pages:
185-193
Main language of publication
English
Received
1995-04-10
Published
1995
Exact and natural sciences