PDF

Discussiones Mathematicae Graph Theory 22(2) (2002) 259-270
DOI: https://doi.org/10.7151/dmgt.1174

GENERALIZED CHROMATIC NUMBERS AND ADDITIVE HEREDITARY PROPERTIES OF GRAPHS

Izak Broere, Samantha Dorfling and Elizabeth Jonck

Department of Mathematics
Faculty of Science
Rand Afrikaans University
P.O. Box 524, Auckland Park, South Africa
e-mail: ib@na.rau.ac.za
e-mail: dorflis@sci.uovs.ac.za

Abstract

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. Let P and Q be additive hereditary properties of graphs. The generalized chromatic number χ_Q(P) is defined as follows: χ_Q(P) = n iff P ⊆ Qⁿ but P ⊄ eq Qⁿ⁻¹. We investigate the generalized chromatic numbers of the well-known properties of graphs ℑ_k, O_k, W_k, S_k and D_k.

Keywords: property of graphs, additive, hereditary, generalized chromatic number.

2000 Mathematics Subject Classification: 05C15.

References

[1]	M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037.
[2]	M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishwa International Publication, Gulbarga, 1991) 41-68.
[3]	I. Broere, M.J. Dorfling, J.E Dunbar and M. Frick, A path(ological) partition problem, Discuss. Math. Graph Theory 18 (1998) 113-125, doi: 10.7151/dmgt.1068.
[4]	I. Broere, P. Hajnal and P. Mihók, Partition problems and kernels of graphs, Discuss. Math. Graph Theory 17 (1997) 311-313, doi: 10.7151/dmgt.1058.
[5]	S.A. Burr and M.S. Jacobson, On inequalities involving vertex-partition parameters of graphs, Congr. Numer. 70 (1990) 159-170.
[6]	G. Chartrand, D.P. Geller and S.T. Hedetniemi, A generalization of the chromatic number, Proc. Camb. Phil. Soc. 64 (1968) 265-271, doi: 10.1017/S0305004100042808.
[7]	M. Frick and F. Bullock, Detour chromatic numbers, manuscript.
[8]	P. Hajnal, Graph partitions (in Hungarian), Thesis, supervised by L. Lovász (J.A. University, Szeged, 1984).
[9]	T.R. Jensen and B. Toft, Graph colouring problems (Wiley-Interscience Publications, New York, 1995).
[10]	L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar 1 (1966) 237-238; MR34#1715.
[11]	P. Mihók, Problem 4, p. 86 in: M. Borowiecki and Z. Skupień (eds), Graphs, Hypergraphs and Matroids (Zielona Góra, 1985).
[12]	J. Nesetril and V. Rödl, Partitions of vertices, Comment. Math. Univ. Carolinae 17 (1976) 85-95; MR54#173.

Received 10 March 2001
Revised 3 December 2001