Generalized list colourings of graphs

• Autorzy: Mieczysław Borowiecki , Ewa Drgas-Burchardt , Peter Mihók
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

hereditary property of graphs; list colouring; vertex partition number

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs
• 05C70: Factorization, matching, partitioning, covering and packing

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1995
• Tom: 15
• Numer: 2
• Strony: 185-193

Daty

wydano

1995

otrzymano

1995-04-10

Twórcy

autor

Mieczysław Borowiecki

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

autor

Ewa Drgas-Burchardt

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

autor

Peter Mihók

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

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgt.1016