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

Abstract

top
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.

How to cite

top

Mieczysł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. [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. [2] M. Borowiecki and P. Mihók, Hereditary Properties of Graphs, in: Advances in Graph Theory (Vishwa International Publications, 1991) 41-68. 
  3. [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. [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. [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. [6] G. Chartrand and L. Lesniak, Graphs and Digraphs, Second Edition, (Wadsworth & Brooks/Cole, Monterey, 1986). Zbl0666.05001
  7. [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. [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. [9] T. Gallai, Kritiche Graphen I, Publ. Math. Inst. Hung. Acad. Sci. 8 (1963) 373-395. Zbl0144.23204
  10. [10] T.R. Jensen and B. Toft, Graph Colouring Problems, (Wiley-Interscience Publications, New York, 1995). 
  11. [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. [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. [13] S.K. Stein, B-sets and planar graphs, Pacific J. Math. 37 (1971) 217-224. Zbl0194.56101
  14. [14] C. Thomassen, Color-critical graphs on a fixed surface (Report, Technical University of Denmark, Lyngby, 1995). 
  15. [15] V.G. Vizing, Colouring the vertices of a graph in prescribed colours, Diskret. Analiz 29 (1976) 3-10 (in Russian). 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.