Generalized list colourings of graphs

Mieczysław Borowiecki; Ewa Drgas-Burchardt; Peter Mihók

Discussiones Mathematicae Graph Theory (1995)

  • Volume: 15, Issue: 2, page 185-193
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Mieczysław Borowiecki, Ewa Drgas-Burchardt, and Peter Mihók. "Generalized list colourings of graphs." Discussiones Mathematicae Graph Theory 15.2 (1995): 185-193. <http://eudml.org/doc/270352>.

@article{MieczysławBorowiecki1995,
abstract = {We prove: (1) that $ch_P(G) - χ_P(G)$ can be arbitrarily large, where $ch_P(G)$ and $χ_P(G)$ are P-choice and P-chromatic numbers, respectively, (2) the (P,L)-colouring version of Brooks’ and Gallai’s theorems.},
author = {Mieczysław Borowiecki, Ewa Drgas-Burchardt, Peter Mihók},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hereditary property of graphs; list colouring; vertex partition number; colouring; hereditary property; chromatic number},
language = {eng},
number = {2},
pages = {185-193},
title = {Generalized list colourings of graphs},
url = {http://eudml.org/doc/270352},
volume = {15},
year = {1995},
}

TY - JOUR
AU - Mieczysław Borowiecki
AU - Ewa Drgas-Burchardt
AU - Peter Mihók
TI - Generalized list colourings of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 1995
VL - 15
IS - 2
SP - 185
EP - 193
AB - We prove: (1) that $ch_P(G) - χ_P(G)$ can be arbitrarily large, where $ch_P(G)$ and $χ_P(G)$ are P-choice and P-chromatic numbers, respectively, (2) the (P,L)-colouring version of Brooks’ and Gallai’s theorems.
LA - eng
KW - hereditary property of graphs; list colouring; vertex partition number; colouring; hereditary property; chromatic number
UR - http://eudml.org/doc/270352
ER -

References

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

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.