ArticleOriginal scientific text

Title

Generalized chromatic numbers and additive hereditary properties of graphs

Authors 1, 1, 1

Affiliations

  1. Department of Mathematics, Faculty of Science, Rand Afrikaans University, P.O. Box 524, Auckland Park, South Africa

Abstract

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. Let and be additive hereditary properties of graphs. The generalized chromatic number χ() is defined as follows: χ()=n iff ⊆ ⁿ but n-1. We investigate the generalized chromatic numbers of the well-known properties of graphs ₖ, ₖ, ₖ, ₖ and ₖ.

Keywords

property of graphs, additive, hereditary, generalized chromatic number

Bibliography

  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.
Pages:
259-270
Main language of publication
English
Received
2001-03-10
Accepted
2001-12-03
Published
2002
Exact and natural sciences