DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 22(2) (2002) 259-270
DOI: 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 PQn but P ⊄ eq Qn−1. We investigate the generalized chromatic numbers of the well-known properties of graphs ℑkOkWkSk and Dk.

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