Generalized chromatic numbers and additive hereditary properties of graphs

Izak Broere; Samantha Dorfling; Elizabeth Jonck

Discussiones Mathematicae Graph Theory (2002)

  • Volume: 22, Issue: 2, page 259-270
  • ISSN: 2083-5892

Abstract

top
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 ₖ.

How to cite

top

Izak Broere, Samantha Dorfling, and Elizabeth Jonck. "Generalized chromatic numbers and additive hereditary properties of graphs." Discussiones Mathematicae Graph Theory 22.2 (2002): 259-270. <http://eudml.org/doc/270271>.

@article{IzakBroere2002,
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 ₖ.},
author = {Izak Broere, Samantha Dorfling, Elizabeth Jonck},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {property of graphs; additive; hereditary; generalized chromatic number},
language = {eng},
number = {2},
pages = {259-270},
title = {Generalized chromatic numbers and additive hereditary properties of graphs},
url = {http://eudml.org/doc/270271},
volume = {22},
year = {2002},
}

TY - JOUR
AU - Izak Broere
AU - Samantha Dorfling
AU - Elizabeth Jonck
TI - Generalized chromatic numbers and additive hereditary properties of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2002
VL - 22
IS - 2
SP - 259
EP - 270
AB - 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 ₖ.
LA - eng
KW - property of graphs; additive; hereditary; generalized chromatic number
UR - http://eudml.org/doc/270271
ER -

References

top
  1. [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. Zbl0902.05026
  2. [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. [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. Zbl0912.05048
  4. [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. Zbl0906.05059
  5. [5] S.A. Burr and M.S. Jacobson, On inequalities involving vertex-partition parameters of graphs, Congr. Numer. 70 (1990) 159-170. Zbl0697.05046
  6. [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. Zbl0173.26204
  7. [7] M. Frick and F. Bullock, Detour chromatic numbers, manuscript. Zbl1002.05021
  8. [8] P. Hajnal, Graph partitions (in Hungarian), Thesis, supervised by L. Lovász (J.A. University, Szeged, 1984). 
  9. [9] T.R. Jensen and B. Toft, Graph colouring problems (Wiley-Interscience Publications, New York, 1995). Zbl0971.05046
  10. [10] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar 1 (1966) 237-238; MR34#1715. Zbl0151.33401
  11. [11] P. Mihók, Problem 4, p. 86 in: M. Borowiecki and Z. Skupień (eds), Graphs, Hypergraphs and Matroids (Zielona Góra, 1985). 
  12. [12] J. Nesetril and V. Rödl, Partitions of vertices, Comment. Math. Univ. Carolinae 17 (1976) 85-95; MR54#173. Zbl0344.05150

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.