On generating sets of induced-hereditary properties

Gabriel Semanišin

Discussiones Mathematicae Graph Theory (2002)

  • Volume: 22, Issue: 1, page 183-192
  • ISSN: 2083-5892

Abstract

top
A natural generalization of the fundamental graph vertex-colouring problem leads to the class of problems known as generalized or improper colourings. These problems can be very well described in the language of reducible (induced) hereditary properties of graphs. It turned out that a very useful tool for the unique determination of these properties are generating sets. In this paper we focus on the structure of specific generating sets which provide the base for the proof of The Unique Factorization Theorem for induced-hereditary properties of graphs.

How to cite

top

Gabriel Semanišin. "On generating sets of induced-hereditary properties." Discussiones Mathematicae Graph Theory 22.1 (2002): 183-192. <http://eudml.org/doc/270532>.

@article{GabrielSemanišin2002,
abstract = {A natural generalization of the fundamental graph vertex-colouring problem leads to the class of problems known as generalized or improper colourings. These problems can be very well described in the language of reducible (induced) hereditary properties of graphs. It turned out that a very useful tool for the unique determination of these properties are generating sets. In this paper we focus on the structure of specific generating sets which provide the base for the proof of The Unique Factorization Theorem for induced-hereditary properties of graphs.},
author = {Gabriel Semanišin},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {induced-hereditary property of graphs; additivity; reducibility; generating sets; maximal graphs; unique factorization; graph property},
language = {eng},
number = {1},
pages = {183-192},
title = {On generating sets of induced-hereditary properties},
url = {http://eudml.org/doc/270532},
volume = {22},
year = {2002},
}

TY - JOUR
AU - Gabriel Semanišin
TI - On generating sets of induced-hereditary properties
JO - Discussiones Mathematicae Graph Theory
PY - 2002
VL - 22
IS - 1
SP - 183
EP - 192
AB - A natural generalization of the fundamental graph vertex-colouring problem leads to the class of problems known as generalized or improper colourings. These problems can be very well described in the language of reducible (induced) hereditary properties of graphs. It turned out that a very useful tool for the unique determination of these properties are generating sets. In this paper we focus on the structure of specific generating sets which provide the base for the proof of The Unique Factorization Theorem for induced-hereditary properties of graphs.
LA - eng
KW - induced-hereditary property of graphs; additivity; reducibility; generating sets; maximal graphs; unique factorization; graph property
UR - http://eudml.org/doc/270532
ER -

References

top
  1. [1] B. Bollobás and A.G. Thomason, Hereditary and monotone properties of graphs, in: R.L. Graham and J. Nesetril, eds., The mathematics of Paul Erdős, II, Algorithms and Combinatorics 14 (Springer-Verlag, 1997) 70-78. Zbl0866.05030
  2. [2] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, Survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. Zbl0902.05026
  3. [3] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishwa International Publication, Gulbarga, 1991) 42-69. 
  4. [4] I. Broere and J.Bucko, Divisibility in additive hereditary graph properties and uniquely partitionable graphs, Tatra Mountains Math. Publications 18 (1999) 79-87. Zbl0951.05034
  5. [5] G. Chartrand, D. Geller and S. Hedetniemi, Graphs with forbidden subgraphs, J. Combin. Theory (B) 10 (1971) 12-41, doi: 10.1016/0095-8956(71)90065-7. Zbl0223.05101
  6. [6] E.J. Cockayne, Color classes for r-graphs, Canad. Math. Bull. 15 (3) (1972) 349-354, doi: 10.4153/CMB-1972-063-2. Zbl0254.05106
  7. [7] E.J. Cockayne, G.G. Miller and G. Prins, An interpolation theorem for partitions which are complete with respect to hereditary properties, J. Combin. Theory (B) 13 (1972) 290-297, doi: 10.1016/0095-8956(72)90065-2. Zbl0268.05006
  8. [8] M. Frick, A survey of (m,k)-colorings, in: J. Gimbel c.a, ed., Quo Vadis, Graph Theory? A source book for challenges and directions, Annals of Discrete Mathematics 55 (North-Holland, Amsterdam, 1993) 45-57. 
  9. [9] S.T. Hedetniemi, On hereditary properties of graphs, J. Combin. Theory (B) 14 (1973) 94-99, doi: 10.1016/S0095-8956(73)80009-7. Zbl0249.05116
  10. [10] T.R. Jensen and B. Toft, Graph colouring problems (Wiley-Interscience Publications, New York, 1995). Zbl0971.05046
  11. [11] P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: M. Borowiecki and Z. Skupień, eds., Graphs, hypergraphs and matroids (Zielona Góra, 1985) 49-58. Zbl0623.05043
  12. [12] P. Mihók, Unique factorization theorem, Discuss. Math. Graph Theory 20 (2000) 143-154, doi: 10.7151/dmgt.1114. Zbl0968.05032
  13. [13] P. Mihók, G. Semanišin and R. Vasky, Additive and Hereditary Properties of Graphs are Uniquely Factorizable into Irreducible Factors, J. Graph Theory 33 (2000) 44-53, doi: 10.1002/(SICI)1097-0118(200001)33:1<44::AID-JGT5>3.0.CO;2-O Zbl0942.05056
  14. [14] J. Mitchem, Maximal k-degenerate graphs, Utilitas Math. 11 (1977) 101-106. Zbl0348.05109

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.